$\mathtt{\text{Minecraft}}$ là một tựa game sandbox từng rất phổ biến trong những năm 2015 - 2017, đồng thời nó cũng là tuổi thơ của rất nhiều giới trẻ hiện tại. Nhóm bạn của tạ thần thỉnh thoảng lại rủ LamTer chơi những trò chơi đối kháng mạnh mẽ như $\mathtt{\text{Bedwars}}$. Tuy nhiên LamTer luôn trốn tránh với lý do tuổi già, vì vậy nhóm bạn đành chuyển sang chơi sáng tạo cho nhẹ nhẹ chill chill và công việc của LamTer chỉ đơn giản là đổ đầy nước cho một cái hồ bơi.

Vì bận chơi $\mathtt{\text{Kai’sa top}}$ nên LamTer đành phải nhờ bạn làm thay công việc của cậu ấy. Công việc của bạn là đổ đầy hồ bơi hình chữ nhật, có diện tích $n\times m$. Trong $\mathtt{\text{Minecraft}}$, khi đổ nước tại một ô $(x,y)$ sẽ tạo ra một nguồn nước, nguồn nước sẽ chảy ra 4 ô xung quanh tạo thành ô cận nguồn nước, các ô cận nguồn nước của các nguồn nước khác nhau có thể kết hợp lại tạo thành một nguồn nước mới.

Vì mỗi lần đổ nước bạn phải bấm chuột phải, điều đó dẫn đến giảm độ bền của chuột nên bạn hãy tìm cách để lấp đầy hồ bơi bằng nguồn nước với số lần đổ nước ít nhất.

$\mathtt{\text{Input}}$

• Gồm 2 số nguyên $n,m$.

$\mathtt{\text{Output}}$

• Gồm một số nguyên duy nhất là số lần đổ nước ít nhất thỏa mãn yêu cầu.

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

2 3

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

3

$\mathtt{\text{Constraint}}$

• $1\le n,m\le {10}^7$

$\mathtt{\text{Subtask}}$

• Subtask $1(30\mathrm{\%})$: $n,m\le 5$.
• Subtask $2(70\mathrm{\%})$: Không có giới hạn gì thêm.

Buổi hòa nhạc của lamter có $N\times M$ chỗ ngồi và $\frac{N\times M}{2}$ cặp đôi đến tham dự. Chỗ ngồi của họ đã được đặt trước.

Tuy nhiên một vài người họ đã không hài lòng và đã đề nghị đổi vị trí với nhau sao cho cặp đôi nào cũng được ngồi gần nhau. Một cặp đôi được gọi là ngồi gần nhau khi họ ngồi cạnh nhau cùng hàng hoặc ngồi cạnh nhau cùng cột.

Để đảm bảo trật tự cho buổi hòa nhạc bạn hãy giúp họ chọn ra số người ít nhất được đổi chỗ để cặp đôi nào cũng được ngồi gần nhau.

$\mathtt{\text{Input}}$

• Dòng đầu tiên chứa hai số nguyên $N$ và $M$ là kích thước của khán đài.
• $N$ dòng tiếp theo mỗi dòng chứa $M$ số nguyên $x$ ($1\le x\le \frac{N\times M}{2}$), các cặp đôi được biểu thị bởi các số nguyên giống nhau.

$\mathtt{\text{Output}}$

• Gồm một dòng duy nhất là số người tối thiểu cần được đổi chỗ.

$\mathtt{\text{Constraint}}$

• $N$, $M\le 80$.
• Dữ liệu đảm bảo không có ai phải đi một mình.

$\mathtt{\text{Subtask}}$

• Subtask $1(30\mathrm{\%})$: $N$, $M\le 8$.
• Subtask $2(70\mathrm{\%})$: Không có giới hạn gì thêm.

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

4 3
1 2 2
3 1 4
5 5 6
3 6 4

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

4

$\mathtt{\text{Note}}$

• Các vị trí cần đổi chỗ là $(2,1)$, $(2,2)$, $(4,2)$, $(4,3)$.

Thành phố $\mathtt{\text{QHHOJ}}$ đang trong quá trình đổi mới với mục tiêu "Không để ai phải đi xe một mình" , chính vì thế ban quản trị quyết định xây dựng các tuyến xe bus hoàn toàn mới nhằm phục vụ cho nhu cầu sử dụng của người dân. Được biết thành phố bây giờ đang có $n$ địa điểm đang được xây dựng làm trạm dừng xe và $m$ con đường một chiều giữa $2$ thành phố liền kề $u,v$ (Giữa hai thành phố có thể có nhiều con đường nhưng mỗi con đường chỉ được nối giữa $2$ thành phố).

Dựa theo kế hoạch, $D$ tuyến xe bus khác nhau sẽ được xây dựng bởi đội ngũ chuyên nghiệp của CodeTN. Với tầm nhìn nhầm chiến lược và nổi trội của mình anh ta đã phát hiện ra rằng trạm $C$ là trạm đặc biệt bởi được xây dựng ở giữa trung tâm thành phố $\mathtt{\text{QHHOJ}}$, gần với các trung tâm thương mại, trường học,... dẫn đến đây luôn là một trong nhưng trạm có nhu cầu sử dựng cao nhất. Chính vì vậy CodeTN quyết định tất cả các tuyến sắp được xây phải đi qua thành phố này và không được bắt đầu hay kết thúc tại thành phố $C$, bên cạnh đó còn định nghĩa rằng $2$ tuyến xe bus được gọi là giống nhau nếu giống nhau điểm đầu và điểm cuối. CodeTN quyết tâm hoàn thành kế hoạch với chi phí nhỏ nhất nhưng vẫn chưa biết phải làm sao, vì vậy hôm nay nhiệm vụ của các bạn là giúp anh ấy hoàn thành kế hoạch của mình một cách tốt nhất.

$\mathtt{\text{Input}}$

• Dòng đầu tiên là $4$ số tự nhiên $n,m,D,C$ ($C\le n\le {10}^5;m\le 5\ast {10}^5;D\le 1000$), lần lượt là số trạm xe bus, số con đường một chiều, số tuyến xe bus phải xây dựng và trạm đặc biệt theo cách nhìn của CodeTN.

• $m$ dòng tiếp theo mỗi dòng gồm $3$ số tự nhiên $u,v,len$ ($u,v\le n;len\le {10}^9$), thể hiện rằng có một con đường một chiều từ $u$ đến $v$ với độ dài là $len$.

$\mathtt{\text{Output}}$

• Một dòng duy nhất là tổng đường đi ngắn nhất tìm được khi xây dựng các tuyến xe bus theo kế hoạch đề ra.
• Nếu không có cách nào xây các tuyến xe bus phù hợp in ra $-1$.

$\mathtt{\text{Subtask}}$

• Subtask $1$ ($40\mathrm{\%}$ số điểm) ($n\le {10}^2;m\le {10}^4$)
• Subtask $2$ ($60\mathrm{\%}$ số điểm) Không có giới hạn gì thêm)

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

3 4 2 1
1 2 9
3 2 28
2 1 3
2 3 11

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

35

Cho một dãy gồm $N$ số $a_1,a_2,...,a_N$. Bạn cần thực hiện $Q$ thao tác truy vấn / cập nhật sau:

• $\mathtt{\text{1 l r v}}$: Lấy một đoạn số $[l,r]$, tăng mỗi số lên $v$ đơn vị. Nói cách khác, với mọi $i\in [l,r]$ gán $a_i:=a_i+v$.
• $\mathtt{\text{2 l r}}$: Tính giá trị của biểu thức $\sum _{i=l}^{r}f(a_i)\mathrm{mod}998244353$.

Trong đó $f(x)=A^x\times x^B$ với $A,B$ được cho trước.

$\mathtt{\text{Input}}$

• Dòng $1$: chứa ba số nguyên $N,Q,A,B$.
• Dòng $2$: chứa $N$ số nguyên dương $a_1,a_2,...,a_N$.
• Dòng $3\to Q+2$: mỗi dòng mô tả một thao tác cập nhật hoặc truy vấn, có dạng như đã miêu tả ở trên.

$\mathtt{\text{Output}}$

• Gồm một số dòng chứa đáp án của các truy vấn loại $2$.

$\mathtt{\text{Constraint}}$

• $N,Q\le {10}^5$.
• $A,B\le 20$.
• $v\le {10}^9$.

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

5 7 1 1
5 9 10 2 1
1 2 3 8
1 1 5 7
2 3 5
1 3 5 4
1 3 5 4
1 4 5 2
2 3 4

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

42
52

$\mathtt{\text{Subtask}}$

• Các test được sinh và sắp xếp theo thứ tự hoàn toàn ngầu nhiên.

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$.