Hiện tại, bạn đang nghiên cứu một thuật toán duyệt cây được gọi là Depth First Search - DFS. Giả sử bạn có một cây gốc gồm \(n\) nút (được đánh số từ \(1\) đến \(n\)) với độ sâu là \(K\) (được đánh số từ \(1\) đến \(K\)). Gốc cây (nút ở độ sâu \(1\)) được đặt tại nút \(1\). Tất cả các lá đều nằm ở cùng một độ sâu, tức là ở độ sâu \(K\). Nút \(i\) có một mảng các nút con \(adj_i\) (có thể trống nếu \(i\) là lá). Mã giả của thuật toán được trình bày như sau:

DFS(u, depth):
    khởi tạo res là một mảng rỗng
    thêm depth vào cuối của res

    duyệt từng đỉnh v trong adj[u]:
        khởi tạo D là mảng kết quả của DFS(v, depth + 1)
        duyệt từng x thuộc D:
            thêm x vào cuối res

    return res

Ví dụ, giá trị trả về của DFS(1, 1) đối với cây bên trái và cây bên phải lần lượt là \([1, 2, 3, 3, 3]\) và \([1, 2, 3, 2, 3]\).

Ký hiệu \(f_K(n)\) là số lượng các giá trị trả về khác biệt của DFS(1, 1) trên tất cả các cây gồm \(n\) nút và tất cả các lá đều nằm ở độ sâu \(K\).

Bạn được cho \(M\) số nguyên: \(A_1, A_2, \ldots, A_M\). Xác định giá trị của \(f_K(A_1) \times f_K(A_2) \times \cdots \times f_K(A_M)\).

Vì kết quả có thể rất lớn, hãy tìm đáp án modulo \(998,244,353\).

Input

• Dòng đầu tiên gồm hai số nguyên \(K\) và \(M\) (\(1 \leq K, M \leq 10^5\)).
• Dòng tiếp theo gồm \(M\) số nguyên \(A_i\) (\(K \leq A_i \leq 2 \times 10^5\)).

Output

• In ra một số nguyên duy nhất đại diện cho giá trị của \(f_K(A_1) \times f_K(A_2) \times \cdots \times f_K(A_M)\) modulo \(998,244,353\).

Subtask

• Subtask \(1\): \(a_i \le 8\) \((20\%)\)
• Subtask \(2\): \(a_i \le 1000\) \((30\%)\)
• Subtask \(3\): Không giới hạn gì thêm.

Sample

Input 1

3 2
5 6

Output 1

6

Explanation 1

• \(f_3(5) = 2\), $f_3(6) = 3 $. Hình dưới đây là minh họa cho các dạng cây có \(6\) đỉnh.
  

Input 2

69696 1
200000

Output 2

920040834

Có \(n\) đồ vật được đánh số từ \(1\) tới \(n\). Đồ vật thứ \(i\) có trọng lượng là \(w_i\) và có giá trị là \(v_i\).

Bạn cần trả lời \(q\) truy vấn, truy vấn thứ \(i\) gồm ba số nguyên \(l_i\), \(r_i\) , \(W_i\), hỏi rằng giả sử nếu chỉ xét các đồ vật trong đoạn \([l_i,r_i]\), thì với tổng trọng lượng tối đa là \(W_i\), bạn có thể thu được tổng giá trị lớn nhất là bao nhiêu? Biết rằng mỗi đồ vật trong đoạn đó bạn chỉ có thể lấy tối đa một lần.

Input

• Dòng đầu gồm số nguyên dương \(n\) \((1 \le n \le 10^4)\)
• \(n\) dòng sau, dòng thứ \(i\) gồm hai số nguyên dương miêu tả đồ vật thứ \(i\): \(w_i\) và \(c_i\) \((1 \le w_i \le 100, c_i \le 10^4)\).
• Dòng tiếp theo gồm số nguyên dương \(q\) miêu tả số truy vấn \((q \le 10^5)\).
• \(q\) dòng sau, dòng thứ \(i\) gồm ba số nguyên dương miêu tả truy vấn thứ \(i\): \(l_i\), \(r_i\), \(W_i\) \((1 \le l_i \le r_i \le n; 1 \le W_i \le 100)\).

Output

• Gồm \(q\) dòng, dòng thứ \(i\) là kết quả của truy vấn thứ \(i\).

Subtask

• Subtask \(1\): \(r-l \le 100\) \((40\%)\)
• Subtask \(2\): \(q \le 10^4\) \((30\%)\)
• Subtask \(3\): Không giới hạn gì thêm \((30\%)\)

Example

Sample Input 1

4
2 15
2 20
4 36
1 4
3
1 2 4
1 4 7
3 4 2

Sample Output 1

35
60
4

Vương quốc \(Ams\) gồm \(n\) thành phố được liên kết với nhau bằng \(m\) con đường hai chiều, đảm bảo rằng mọi cặp thành phố đều có đường đi trực tiếp hoặc gián tiếp tới nhau. Con đường thứ \(i\) kết nối hai thành phố \(u_i,v_i\), và sẽ tốn \(w_i\) lít xăng để đi qua.

Là một người đam mê du lịch, bạn lên kế hoạch cho chuyến đi chơi của mình tới \(Ams\). Bạn xuất phát từ thành phố \(st\) và có dự định đi tới thành phố \(en\) bằng xe của mình. Tất nhiên đi xe thì phải tốt nhiên liệu, và xe của bạn có một bình xăng chứa được tối đa \(t\) lít xăng.

\(Ams\) có \(s\) trạm xăng. Trạm xăng thứ \(i\) được phân bố ở thành phố \(p_i\) và có chi phí cho mỗi lít xăng là \(c_i\). Ở mỗi trạm xăng, bạn có thể mua không giới hạn số xăng (tất nhiên xe bạn chỉ mang tối đa được \(t\) lít xăng thôi).

Bạn bắt đầu từ thành phố \(st\) và xe bạn ban đầu không có xăng - may mắn rằng đảm bảo luôn có trạm xăng ở thành phố nơi bạn xuất phát. Hãy tính số tiền ít nhất cần bỏ ra để hoàn thành hành trình từ \(st\) tới \(en\).

Input

• Dòng đầu gồm \(3\) số nguyên dương \(n,m,s\) \((2 \le n \le 1000; 1 \le m \le 10^4; 1 \le s \le 100)\)
• Dòng tiếp theo gồm một số nguyên dương \(t\) \((1 \le t \le 10^5)\) mô tả sức chứa của bình xăng.
• \(m\) dòng tiếp theo, dòng thứ \(i\) gồm ba số nguyên dương \(u_i,v_i,w_i\) \((1 \le u_i, v_i \le n; 1 \le w_i \le t)\) miêu tả con đường thứ \(i\).
• \(s\) dòng tiếp theo, dòng thứ \(i\) gồm hai só nguyên dương \(p_i,c_i\) \((1 \le p_i \le n; 1 \le c_i \le 100)\) miêu tả trạm xăng thứ \(i\).
• Dòng cuối cùng gồm hai số nguyên dương \(st,en\) \((1 \le st, en \le n)\) miêu tả vị trí ban đầu và đích đến của bạn.

Output

• In ra số tiền ít nhất cần để di chuyển.

Subtask

• Subtask \(1\) \((30\%)\): \(n \le 100; m \le 100; t \le 500\)
• Subtask \(2\) \((30\%)\): \(t \le 500\)
• Subtask \(3\) \((40\%)\): Không giới hạn gì thêm.

Sample Input 1:

3 3 2
200
1 3 80
1 2 50
2 3 50
1 70
2 40
1 3

Sample Output 1:

5500

Sample Input 2:

5 5 3
100
1 2 80
2 5 80
1 3 40
3 4 60
4 5 60
1 8
2 9
3 2
1 5

Sample Output 2:

1340

Sample Input 3:

4 3 3
10
1 2 2
2 3 6
3 4 3
1 4
2 7
3 9
2 4

Sample Output 3:

61

Cho ma trận vuông \(n \times n\), các hàng được đánh số từ \(1\) tới \(n\), các cột được đánh số từ \(1\) tới \(n\). Các ô được sắp xếp theo thứ tự từ trái sang phải, từ trên xuống dưới, ô \((i,j)\) có giá trị là \(a_{i,j}\).

Ivan Tèo đang đứng ở ô \((1,1)\) của ma trận, trong mỗi lần đi, cậu chỉ có thể đi sang phải hoặc xuống dưới, nói cách khác, nếu đang ở ô \((i,j)\), cậu chỉ có thể đi sang ô \((i+1,j)\) hoặc \((i,j+1)\). Gọi \(Best(i,j)\) là giá trị lớn nhất có thể nếu Ivan Tèo đi từ ô \((1,1)\) tới ô \((i,j)\). Vì cảm thấy rằng nếu chỉ hỏi các \(Best(i,j)\) thì quả là nhàm chán và không đánh giá đúng được tiềm năng của Tèo, \(mrhee\) quyết định tạo ra một giá trị mới như sau:

• Gọi \(S\) là tổng các \(Best(i,j)\) của mọi ô \((i,j)\) trên ma trận.
• Nói cách khác, \(S = \sum Best(i,j)\), với mọi \((1 \le i,j \le n)\).

Vì lại cảm thấy việc in ra \(S\) của ma trận hiện tại là quá dễ với Tèo, \(mrhee\) quyết định tạo ra \(q\) sự thay đổi, sự thay đổi thứ \(i\) có dạng như sau:

• Cho ba số nguyên \(u_i,v_i,delta_i\) \((1 \le u_i,v_i \le n, -1\le delta_i \le 1)\), tức gán giá trị \(a_{u_i,v_i} = a_{u_i,v_i} + delta_i\).
• Sau mỗi truy vấn, hãy in ra giá trị \(S\) của ma trận mới.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n,q\) \((1 \le n \le 1000, 1 \le q \le 3 \times 10^4)\)
• \(n\) dòng sau, dòng thứ \(i\) gồm \(n\) số nguyên, số thứ \(j\) miêu tả giá trị \(a_{i,j}\) \((-10^2 \le a_{i,j} \le 10^2)\) của ma trận.
• \(q\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(u_i,v_i,delta_i\) \((1 \le u_i,v_i \le n, -1 \le delta_i \le 1)\) miêu tả truy vấn thứ \(i\).

Output:

• Gồm một dòng in ra số cặp \((i,j)\) thỏa mãn.

Subtask:

• Subtask \(1\) (\(25\%\) số điểm): \(q \le 10\).
• Subtask \(2\) (\(25\%\) số điểm): Ô \((u_i,v_i)\) trong mọi truy vấn là giống nhau và \(q \le 3000\), đồng thời \(delta_i = 1\) với mọi truy vấn.
• Subtask \(3\) (\(30\%\) số điểm): \(q \le 3000\)
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Sample Input 1

2 2
1 2
2 2
1 2 0
2 1 1

Sample Output 1

12
14

Sample Input 2

4 4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
1 1 1
2 2 -1
3 1 1
1 3 -1

Sample Output 2

196
195
203
199

Explanation

Ở ví dụ \(1\), sau truy vấn đầu, bảng không thay đổi gì, ta có các \(Best(i,j)\) như sau:

• \(Best(1,1) = 1\)
• \(Best(1,2) = 3\)
• \(Best(2,1) = 3\)
• \(Best(2,2) = 5\)

Sau khi tăng ô \((2,1)\) lên \(4\) đơn vị, ta có:

• \(Best(1,1) = 1\)
• \(Best(1,2) = 3\)
• \(Best(2,1) = 4\)
• \(Best(2,2) = 6\)