Bài tập

Vương quốc Lakasi là một vương quốc mới thành lập, nhà vua muốn mở rộng phạm vi lãnh thổ nên quyết định đi khai phá các vùng đất mới. Nhà vua quyết định mỗi một vùng đất sau khi khai thác thì xây dựng một thành phố ở đó cùng với đó là các con đường nối giữa các thành phố với nhau sao cho khi hoàn thành công việc mở rộng lãnh thổ thì tất cả các thành phố và các con đường tạo thành một đồ thị dạng cây. Hiện ban đầu nhà vua đang ở thủ đô và xem đó như là đỉnh \(1\). Các thành phố còn lại xem như là các đỉnh con trong cây có gốc là đỉnh \(1\). Trong quá trình xây dựng, có \(Q\) sự kiện diễn ra gồm 2 loại:

• Add x y -- thêm một đỉnh mới là một đỉnh con có đường đi độ dài \(y\) nối với đỉnh \(x\). Đỉnh mới được thêm sẽ có chỉ số bằng số lượng đỉnh trong đồ thị hiện tại.

• Query a b -- Nhà vua muốn biết độ dài đường đi dài nhất bắt đầu từ đỉnh \(a\) đến một đỉnh bất kỳ nằm trong cây con gốc \(b\) là bao nhiêu. Độ dài của một đường đi được tính bằng tổng xor (exclusive or) của tất cả các con đường thuộc đường đi đó.

Đối với sự kiện loại 2, hãy trả lời câu hỏi của nhà vua.

Input

• Dòng đầu tiên chứa một số nguyên dương \(Q\) \((Q\leq 200000)\).

• \(Q\) dòng tiếp theo, mỗi dòng có dạng 1 trong 2 sự kiện trên. Các giá trị \(x,a,b\) không vượt quá số lượng đỉnh hiện tại, giá trị \(y\) không quá \(2^{30}\).

Output

• Với sự kiện loại 2, hãy in ra đường đi dài nhất bắt đầu từ đỉnh \(a\) đến một đỉnh bất kỳ nằm trong cây con gốc \(b\).

Example

4
Add 1 5
Query 1 1
Add 1 7
Query 1 1

5
7

Scoring

• Subtask 1 (\(10\%\) số điểm): \(Q\leq 200\).

• Subtask 2 (\(25\%\) số điểm): \(Q\leq 2000\).

• Subtask 3 (\(25\%\) số điểm): Tất cả sự kiện loại 2 đều có \(b=1\).

• Subtask 4 (\(40\%\) số điểm): Không có giới hạn gì thêm.

Có \(n\) học sinh tham gia một kì thi gồm hai phần: Toán học và Tin học. Học sinh thứ \(i\) (\(1 \le i \le n\)) đạt \(S_i\) điểm phần Toán và \(T_i\) điểm phần Tin.

Hai giáo sư là giáo sư T và giáo sư I sẽ cùng đưa ra quyết định xem học sinh đó có được coi là qua môn hay không, dựa trên các tiêu chí như sau:

• Giáo sư T yêu cầu mỗi học sinh đạt ít nhất \(A\) điểm Toán và ít nhất \(B\) điểm Tin để được qua.
• Giáo sư I chỉ quan tâm tổng điểm: học sinh cần có tổng điểm \(S_i + T_i\) lớn hơn hoặc bằng \(C\) để được qua.
• Một học sinh chỉ được coi là qua môn nếu thỏa mãn cả hai tiêu chí trên.

Tuy nhiên, bạn không biết giá trị cụ thể của \(A\), \(B\), và \(C\). Thay vào đó, bạn nhận được \(q\) bộ ba số nguyên \((X_j, Y_j, Z_j)\) tương ứng với các bộ tiêu chí \((A, B, C)\).

Với mỗi bộ tiêu chí \((X_j, Y_j, Z_j)\), hãy tính xem có bao nhiêu học sinh qua môn.

\InputFile

• Dòng đầu chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(S_i\) và \(T_i\) (\(0 \le S_i, T_i \le 10^9\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(X_j, Y_j, Z_j\) (\(0 \le X_j, Y_j \le 10^9\), \(0 \le Z_j \le 2 \cdot 10^9\)).

\OutputFile

In ra \(q\) dòng, dòng thứ \(j\) là số học sinh qua môn ứng với bộ tiêu chí \((A = X_j, B = Y_j, C = Z_j)\).

\Scoring

• Subtask 1 (10%): \(n, q \le 3000\)
• Subtask 2 (22%): \(S_i, T_i \le 10^5\), \(X_j, Y_j \le 10^5\), \(Z_j = 0\)
• Subtask 3 (40%): \(S_i, T_i \le 10^5\), \(X_j, Y_j \le 10^5\), \(Z_j \le 2 \cdot 10^5\)
• Subtask 4 (28%): Không có ràng buộc bổ sung

\Examples

\beginexample
\exmp
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
2
4
1
1

\endexample

Cho một quân mã được đặt trên mặt phẳng tọa độ Descartes. Trong mỗi bước di chuyển, quân mã có thể đi theo một trong bốn vector chỉ phương \((2, -1)\); \((2, 1)\); \((1, 2)\) và \((-1, 2)\) như hình vẽ dưới đây:

\begincenter

\endcenter

Cho biết quân mã đang ở điểm có tọa độ \((x_1, y_1)\) và quân mã cần đi tới điểm có tọa độ \((x_2, y_2)\). Hãy đếm số cách quân mã có thể làm được điều này. Do kết quả có thể rất lớn, hãy in ra theo modulo \(998244353\).

Input

Dòng đầu tiên chứa số nguyên \(t\) \((1 \leq t \leq 10^5)\) là số câu hỏi.

\(t\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\) \((1 \leq x_1, y_1, x_2, y_2 \leq 2000)\) cho biết vị trí xuất phát và vị trí cần tới của quân mã.

Output

In ra \(t\) số nguyên là đáp án của \(t\) câu hỏi \(–\) số cách để quân mã đi từ vị trí xuất phát tới vị trí kết thúc, theo modulo \(998244353\).

Example

3
2 3 5 3
1 1 2 3
2 2 1 1

3
1
0

Scoring

• Subtask \(1\) (\(20\) điểm): \(x_1, y_1, x_2, y_2 \leq 5\)

• Subtask \(2\) (\(15\) điểm): \(x_1, y_1, x_2, y_2 \leq 100\) và \(t \leq 10\)

• Subtask \(3\) (\(15\) điểm): \(x_1, y_1, x_2, y_2 \leq 100\)

• Subtask \(4\) (\(25\) điểm): \(x_1, y_1, x_2, y_2 \leq 2000\) và \(t \leq 10\)

• Subtask \(5\) (\(25\) điểm): Không có ràng buộc gì thêm.

Một khu vườn có thể xem như một lưới hình chữ nhật có kích thước \(N \times M\). Các dòng được đánh số từ \(1\) đến \(N\), các cột được đánh số từ \(1\) đến \(M\). Giao điểm giữa dòng \(i\) (\(1 \le i \le N\)) và cột \(j\) (\(1 \le j \le M\)) là ô \((i,j)\), và người ta muốn trồng hoa trên khu vườn này.

Trên khu vườn đã lắp đặt sẵn \(Q\) máy phun nước và \(K\) máy phun phân vi sinh. Một ô có thể chứa đồng thời nhiều máy phun nước và phân vi sinh.

• Một máy phun nước khi được đặt ở ô \((x, y)\) sẽ tưới nước cho mọi ô \((i,j)\) thỏa mãn \(x \le i\) và \(y \le j\).
• Một máy phun phân vi sinh khi được đặt ở ô \((z, w)\) sẽ tưới phân vi sinh cho mọi ô \((i,j)\) thỏa mãn \(i \le z\) và \(j \le w\).

Một ô trong khu vườn có thể trồng hoa khi ô đó được tưới cả nước và phân vi sinh.

Người ta muốn chọn các khu đất hình chữ nhật có các cạnh song song với biên của khu vườn thỏa mãn điều kiện để trồng hoa.

Yêu cầu: Cho kích thước khu vườn \(N \times M\), vị trí của \(Q\) máy phun nước và \(K\) máy phun phân vi sinh, hãy tính số lượng các khu đất hình chữ nhật có thể chọn để trồng hoa.

Input

• Dòng đầu tiên chứa bốn số \(N, M, Q, K\) (\(1 \le Q, K \le 3 \times 10^5\); \(Q, K \le N \times M\), \(1 \le N, M \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số \(x, y\) là vị trí của một máy phun nước.
• \(K\) dòng tiếp theo, mỗi dòng chứa hai số \(z, w\) là vị trí của một máy phun phân vi sinh.

Output

• Một dòng ghi một số nguyên là kết quả của bài toán sau khi chia lấy dư cho \(10^9 + 7\).

Example

3 3 2 1
1 2
2 1
3 2

12

Scoring

• 20% số tests tương ứng với 20% điểm của bài có: \(N, M \le 100\);
• 20% số tests khác tương ứng với 20% điểm của bài có: \(N, M \le 4000\);
• 20% số tests khác tương ứng với 20% điểm của bài có: \(N \le 4000\);
• 20% số tests khác tương ứng với 20% điểm của bài có: \(N \le 3 \times 10^5\);
• 20% số tests còn lại tương ứng với 20% điểm của bài có không có ràng buộc gì thêm.