Du hành thời gian là một khái niệm khoa học viễn tưởng rất phổ biến trong các bộ phim, đây là một chủ đề khơi dậy sự tò mò của rất nhiều người và đồng thời cũng có tạo ra rất nhiều nghịch lý xoắn não.

Có thể thấy rằng việc du hành thời gian sẽ tạo ra nhiều vấn đề như nghịch lý ông nội hay nghịch lý tiền định như trong bộ phim $\mathtt{\text{Predestination}}$ khi nhân vật chính vừa là cha vừa là mẹ vừa là sếp vừa là kẻ thù của chính bản thân mình. Có rất nhiều giả thuyết được đưa ra để giải thích các nghịch lý về việc du hành thời gian. Tuy nhiên phổ biến nhất vẫn là $2$ giả thuyết sau.

Đầu tiên sẽ phải kể đến giả thuyết tự sửa chữa của dòng thời gian, tức là bạn sẽ không thể làm bất cứ điều gì để thay đổi được hiện tại, hành động của bạn chỉ thúc đẩy cho hiện tại xảy ra. Ví dụ như bạn quay lại quá khứ để ngăn chặn một vụ tai nạn xe hơi nhưng lại không ngờ rằng bạn lại là nguyên nhân của vụ tai nạn. Ta có thể thấy giả thuyết này trong các bộ phim khoa học viễn tưởng như: Predesination, Interstellar, Tenet, Time Crime...

Tiếp theo phải kể đến câu chuyện dòng thời gian song song, tức là nếu bạn quay về quá khứ và thay đổi điều gì đó thì bạn sẽ tạo ra một dòng thời gian mới hoàn toàn. Giả thuyết này cũng có sự liên quan chặt chẽ tới vật lý lượng tử, đặc biệt là trong thí nghiệm con mèo của Schrödinger khi mà một vật thể tồn tại song song ở cả $2$ trạng thái cùng một lúc thì một vũ trụ song song sẽ được tạo ra. Nên vậy khi nào mà đứa bạn của bạn bị thất tình thì cứ an ủi nó là: $\mathtt{\text{“}}$Tồn tại ít nhất $1$ vũ trụ mà crush đồng ý lời tỏ tình của mày$\mathtt{\text{”}}$.

Chắc hẳn trong vòng thi đấu đầu tiên của $\mathtt{\text{QHHOJ Summer Challenge 2024}}$ các bạn đã được làm quen với ông Q (heygnauq ở tương lai) và cỗ máy du hành thời gian của ông ấy. Trong lần trước, vì đã du hành quá nhiều nên ông Q đã vô tình tạo ra thêm rất nhiều dòng thời gian, và ông có cơ hội được làm quen với ông Q1 tốt, ông Q2 rìa và ông Q3 hạ gục.

Trong bài toán hôm nay chúng ta sẽ được gặp ông QQtrox (heygnauq ở một vũ trụ song song) và cỗ máy thời gian của ông ấy. Cụ thể ông QQtrox có một cây gồm $n$ đỉnh được đánh số từ $1$, trên đỉnh thứ $i$ có một giá trị $S_i$. Ban đầu giá trị của tất cả các đỉnh đều bằng $0$. Gọi $P(x,y)$ là tập hợp được đánh số từ $1$ của các đỉnh trên đường đi đơn từ đỉnh $x$ đến đỉnh $y$, $P(x,y)$ là một tập hợp có thứ tự, với thứ tự chính là các đỉnh trên đường đi đơn bắt đầu từ $x$ và kết thúc ở $y$. Ông QQtrox có $Q$ truy vấn thuộc một trong các dạng sau:

• $\mathtt{\text{add x y z}}$:
  • Tăng giá trị của tất cả các đỉnh thuộc $P(x,y)$ lên $z$ đơn vị.
  • $1\le x,y\le n;0\le z<{10}^9+7$.
• $\mathtt{\text{res t}}$:
  • Đưa giá trị của tất cả các đỉnh quay về ngay trước truy vấn thứ $t$.
  • Dữ liệu đảm bảo sẽ không du hành tới tương lai (vì tương lai vẫn có thể thay đổi được).
• $\mathtt{\text{sum x y z}}$:
  • Tính tổng $\sum _{i\in P(x,y)}{S_i}^z$.
  • $1\le x,y\le n;1\le z\le 4$.
  • Vì kết quả có thể rất lớn nên hãy ghi ra phần dư khi chia kết quả cho ${10}^9+7$.
• $\mathtt{\text{sin x y}}$: tính tổng $\sum _{i\in P(x,y)}\sin (S_i)$.
  • $1\le x,y\le n$.
  • Đơn vị góc là $\mathtt{\text{radian}}$.
  • Ghi ra kết quả với chính xác $3$ chữ số thập phân.
• $\mathtt{\text{cos x y}}$: tính tổng $\sum _{i\in P(x,y)}\cos (S_i)$.
  • $1\le x,y\le n$.
  • Đơn vị góc là $\mathtt{\text{radian}}$.
  • Ghi ra kết quả với chính xác $3$ chữ số thập phân.

$\mathtt{\text{Input}}$

Dòng đầu tiên chứa số nguyên dương $T$ là số bộ test. Với mỗi bộ test:

• Dòng đầu tiên chứa hai số nguyên $n,Q$ lần lượt là số đỉnh của đồ thị và số truy vấn của ông QQtrox.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v$ ($1\le u,v\le n;u\ne v$) thể hiện rằng có một cạnh nối giữa đỉnh thứ $u$ và đỉnh thứ $v$. Dữ liệu đảm bảo đồ thị tạo thành dạng cây.
• $Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong các dạng đã kể trên.

$\mathtt{\text{Output}}$

• Ghi ra các kết quả của các truy vấn như yêu cầu ở trên, mỗi kết quả được ghi trên một dòng.

$\mathtt{\text{Constraint}}$

• $1\le T\le 10$.
• $1\le n,Q\le {10}^5$.

$\mathtt{\text{Subtask}}$

• Subtask $1$ ($5\mathrm{\%}$ số điểm): $n,Q\le 1000$.
• Subtask $2$ ($5\mathrm{\%}$ số điểm): Không có truy vấn $\mathtt{\text{res}},\mathtt{\text{sin}},\mathtt{\text{cos}}$ và bậc của tất cả các đỉnh đều không lớn hơn $2$.
• Subtask $3$ ($5\mathrm{\%}$ số điểm): Không có truy vấn $\mathtt{\text{sin}},\mathtt{\text{cos}}$ và bậc của tất cả các đỉnh đều không lớn hơn $2$.
• Subtask $4$ ($5\mathrm{\%}$ số điểm): Không có truy vấn $\mathtt{\text{res}}$ và bậc của tất cả các đỉnh đều không lớn hơn $2$.
• Subtask $5$ ($30\mathrm{\%}$ số điểm): Bậc của tất cả các đỉnh đều không lớn hơn $2$
• Subtask $6$ ($5\mathrm{\%}$ số điểm): Không có truy vấn $\mathtt{\text{res}},\mathtt{\text{sin}},\mathtt{\text{cos}}$.
• Subtask $7$ ($5\mathrm{\%}$ số điểm): Không có truy vấn $\mathtt{\text{sin}},\mathtt{\text{cos}}$.
• Subtask $8$ ($5\mathrm{\%}$ số điểm): Không có truy vấn $\mathtt{\text{res}}$.
• Subtask $9$ ($35\mathrm{\%}$ số điểm): Không có giới hạn gì thêm.

$\mathtt{\text{Sample Input}}$

1
5 10
1 2
2 3
3 4
4 5
add 1 5 5
add 1 3 2
add 2 4 7
sin 1 2
cos 3 5
sum 2 3 4
res 2
sin 1 2
cos 3 5
sum 2 3 4

$\mathtt{\text{Sample Output}}$

1.648
1.264
76832
-1.918
0.851
1250

$\mathtt{\text{Notes}}$

• Ban đầu dãy số là $S=\{0,0,0,0,0\}$.
• Sau truy vấn $1$ dãy số trở thành $S=\{5,5,5,5,5\}$.
• Sau truy vấn $2$ dãy số trở thành $S=\{7,7,7,5,5\}$.
• Sau truy vấn $3$ dãy số trở thành $S=\{7,14,14,12,5\}$.
• Kết quả truy vấn $4$ là: $ans=\sin S_1+\sin S_2=\sin 7+\sin 14=1.648$.
• Kết quả truy vấn $5$ là: $ans=\cos S_3+\cos S_4+\cos S_5=\cos 14+\cos 12+\cos 5=1.264$.
• Kết quả truy vấn $6$ là: $ans={S_2}^4+{S_3}^4={14}^4+{14}^4=76832$.
• Truy vấn $7$ đưa dãy số về trước khi truy vấn $2$ xảy ra, dãy số trở thành: $S=\{5,5,5,5,5\}$.
• Kết quả truy vấn $8$ là: $ans=\sin S_1+\sin S_2=\sin 5+\sin 5=-1.918$.
• Kết quả truy vấn $9$ là: $ans=\cos S_3+\cos S_4+\cos S_5=\cos 5+\cos 5+\cos 5=0.851$.
• Kết quả truy vấn $10$ là: $ans={S_2}^4+{S_3}^4=5^4+5^4=1250$.