Bạn được cho một mảng gồm ~n~ số nguyên và nhiệm vụ của bạn là tìm ba giá trị (tại các vị trí phân biệt) có tổng là ~x~.

Input

• Dòng đầu vào đầu tiên có hai số nguyên ~n~ và ~x~: kích thước mảng và tổng mong muốn.
• Dòng thứ hai có ~n~ số nguyên ~a_1,a_2,\ldots,a_n~: các giá trị của mảng.

Output

• In ba số nguyên: vị trí của các giá trị. Nếu có một số lời giải, bạn có thể in bất kỳ lời giải nào trong số đó. Nếu không có lời giải nào, in IMPOSSIBLE.

Constraints

• ~1 \leq n \leq 5000~
• ~1 \leq x, a_i \leq 10 ^ 9~

Example

Sample input

4 8
2 7 5 1

Sample output

1 3 4

Hiếu đi dự đám cưới ở một nhà hàng trong thành phố. Trời nắng nên con đường hành lang đi từ nhà hàng ra bãi giữ xe được che bởi các tấm bạt có kích thước khác nhau (đường hành lang là đường thẳng). Nhưng vì các chú bảo vệ lo nhận và giữ xe nên che các tấm bạt rất lộn xộn chỗ thì khít, chỗ thì chồng lên nhau, chỗ thì hở ra. Hiếu muốn tìm đoạn đường dài nhất trên đường mình đi được che kín bởi các tấm bạt.

Cho ~N~ cặp số [~L_i,R_i~], ~i=1..N~ (~0 \le L_i,R_i\le 60000~) là vị trí đầu và vị trí cuối của mỗi tấm bạt theo chiều dài hành lang.

Yêu cầu: Viết chương trình tìm độ dài lớn nhất của đoạn đường được che kín bởi các tấm bạt.

Input

• Dòng đầu chứa một số nguyên ~N~ (~1< N \le 10000~) là số lượng tấm bạt.
• ~N~ dòng tiếp theo mỗi dòng biểu diễn vị trí của mỗi tấm bạt theo chiều dài hành lang là ~L_i~ và ~R_i~ (mỗi số cách nhau một dấu cách, ~L_i < R_i~).

Output

• Ghi ra một số nguyên duy nhất theo yêu cầu trên.

Sample Tests

Input

7
7 12
0 5
20 25
33 38
6 8
27 34
11 19

Output

13

Explanation

Giải thích: Đoạn đường được che kín dài nhất là từ vị trí 6 đến 19, được che bởi 3 tấm bạt là: ~(6;8), (7;12),(11, 19)~

Cho mảng ~A~ gồm ~n~ số, ban đầu tất cả các phần tử đều bằng ~0~. Có ~q~ thao tác dạng ~(l, r)~ có nghĩa là tăng các phần tử ~A_l, A_{l + 1}, ..., A_r~ lên ~1~ đơn vị.

Có thêm ~m~ truy vấn dạng ~(x, y)~, có nghĩa là thực hiện tất cả thao tác ~q_x, q_{x + 1}, ..., q_y~.

Input

• Dòng đầu tiên gồm 3 số nguyên ~n, q, m (1 \le n, q, m\le 10^5)~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số nguyên ~l, r (1 \leq l \leq r \leq n)~.
• ~m~ dòng tiếp theo mỗi dòng gồm 2 số nguyên ~x, y (1 \leq x \leq y \leq q)~.

Output

• In ra mảng ~A~ sau tất cả các truy vấn.

Sample Test

Input:

3 3 3
1 2
2 3
1 3
2 3
1 2
1 3

Output:

4 7 5

Cho hai dãy ~a~ và ~b~ gồm ~n~ phần tử nguyên dương. Bạn được nhận thêm một số nguyên dương ~k~, hãy đếm số cặp ~(i,j)~ ~(1 \le i,j \le n)~ sao cho ~\overline{a_ib_j}~ ~\vdots~ ~k~.

Nói cách khác, hãy đếm số cặp ~(i,j)~ sao cho số nguyên dương ~X~ được tạo bởi cách viết liền ~a_i~ và ~b_j~ với nhau chia hết cho số nguyên dương ~K~ cho trước.

Ví dụ:

• ~a_i = 5, b_j = 77 \Rightarrow X = 577~
• ~a_i = 66, b_j = 99 \Rightarrow X = 6699~

Input

• Dòng đầu tiên gồm số hai nguyên dương ~n~ và ~k~ ~(1 \le n,k \le 3 \times 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~ ~(1 \le a_i \le 3 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~b_1,b_2,...,b_n~ ~(1 \le b_i \le 3 \times 10^5)~.

Output:

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

Subtask:

• Subtask ~1~ (~40\%~ số điểm): ~n \le 2000~.
• Subtask ~2~ (~30\%~ số điểm): ~a_i,b_j \le 2000~ ~\forall i,j \in [1,n]~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4 3
1 4 3 6
11 2 4 21 

Sample Output 1

6

Explanation 1

Có các cặp sau:

• ~(1,1) = 111~
• ~(1,2) = 12~
• ~(2,1) = 411~
• ~(2,2) = 42~
• ~(3,4) = 321~
• ~(4,4) = 621~

Gọi ~A~ là dãy số với ~A(i)~ được tạo bởi ghép ~i~ số nguyên tố đầu tiên với nhau: ~2, 23, 235, 2357, 235711, 23571113, ... ~.

Cho ~n~ và ~k~, hãy tìm cách xóa ~k~ chữ số ra khỏi số ~A(n)~ để thu được số lớn nhất có thể.

Input

• Gồm một dòng chứa hai số nguyên không âm ~n~ và ~k~ ~(1 \le n \le 50000)~, dữ liệu đảm bảo ~k~ bé hơn số chữ số của ~A(n)~.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 50~.
• ~50\%~ số test không ràng buộc gì thêm.

Sample Input 1:

7 4

Sample Output 1:

711317

Cho số nguyên dương ~n~, hãy tính tổng sau:

• ~S = \lfloor \frac{x}{1} \rfloor + \lfloor \frac{x}{2} \rfloor + ... + \lfloor \frac{x}{n} \rfloor ~

Ở đây, ~\lfloor x \rfloor~ kí hiệu số nguyên dương lớn nhất nhất không vượt quá ~x~.

Input

• Dòng đầu chứa số nguyên dương ~T~ ~(1 \le T \le 30)~ là số lượng bộ test.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ ~(1 \le n \le 10^{12})~

Output

• Gồm ~T~ dòng, mỗi dòng in ra đáp án tương ứng sau khi lấy modulo cho ~10^6~.

Scoring

• 50% số test có ~n \le 10^6~
• 50% số test còn lại không có ràng buộc gì thêm

Sample Input 1

2
1
5

Sample Output 1

1
10

Cho một đồ thị vô hướng có dạng cây, tức là đồ thị gồm ~n~ đỉnh và ~n-1~ cạnh. Các đỉnh được đánh số từ ~1~ tới ~n~, đỉnh thứ ~i~ có trọng số là ~w_i~.

Chắc hẳn các bạn đều biết khái niệm về cây con, giả sử ta có một cây có gốc là ~1~ như sau:

• Cây con có gốc là ~2~ sẽ bao gồm các đỉnh : ~\{2,6,5,4\}~.
• Cây con có gốc là ~3~ sẽ bao gồm các đỉnh : ~\{3\}~.

Ta định nghĩa ~S(root,a)~ là tổng trọng số các đỉnh trong cây con gốc ~a~ khi gốc của cây là ~root~. Hay ~S(root,a) = \sum_u^{u \in subtree(a)} w[u]~ khi gốc của cây là ~root~.

Bạn cần trả lời ~q~ câu hỏi, mỗi câu hỏi có dạng như sau:

• ~a~ ~b~ : Hãy in ra ~S(a,b)~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~ ~(n,q \le 2 \times 10^5)~ miêu tả số đỉnh và số truy vấn.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~w~ ~(1 \le w_i \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~u_i~ và ~v_i~ miêu tả cạnh ~(u_i,v_i)~ của cây ~(1 \le u_i,v_i \le n)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~a_i,b_i~ ~(1 \le a_i,b_i \le n)~ miêu tả truy vấn tương ứng.

Output:

• Với mỗi truy vấn, in ra đáp án tương ứng.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~n,q \le 2000~
• Subtask ~2~ (~25\%~ số điểm): ~a_i = 1~ với mọi truy vấn.
• Subtask ~3~ (~25\%~ số điểm): ~b_i = 1~ với mọi truy vấn.
• Subtask ~4~ (~25\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

10
6
12
3

Explanation 1

Đối với hai truy vấn đầu tiên, gốc của cây bằng ~1~.

• ~S(1,2) = w[2] + w[6] + w[5] + w[4] = 10~
• ~S(1,6) = w[6] + w[5] = 6~

Đối với truy vấn thứ ba, gốc của cây bằng ~4~:

• ~S(4,2) = w[2] + w[6] + w[5] + w[1] + w[3] = 12~

Đối với truy vấn thứ tư, gốc của cây bằng ~2~

• ~S(2,1) = w[1] + w[3] = 3~

Cho một cây gồm ~n~ đỉnh gồm ~n-1~ cạnh. Cạnh thứ ~i~ có dạng ~(u_i,v_i, w_i)~, kết nối đỉnh ~u_i~ với đỉnh ~v_i~ và có độ dài là một số nguyên dương ~w_i~.

Gọi ~D(u,v)~ là khoảng cách giữa hai đỉnh ~u~ và ~v~ trên cây (được tính bằng tổng trọng số trên cạnh mà đường đi từ ~u~ tới ~v~ đi qua). Ta có hàm ~S(i)~ là tổng khoảng cách từ ~i~ tới tất cả các đỉnh trên cây:

• ~S(i) = \sum_{u=1}^{n} D(i,u)~.

Với mỗi đỉnh ~u~ trên cây, bạn được phép thử gán giá trị của một cạnh bất kì trên cây bằng ~0~ (tức là gán một giá trị ~w_i = 0~), sao cho giá trị ~S(u)~ mới, ta tạm gọi là ~S(u)'~ là nhỏ nhất có thể. Lưu ý rằng, mỗi lần thử là độc lập với nhau, ta không thực sự gán cạnh nào bằng ~0~ trong cây gốc cả.

Để tránh biến bài toán quá khó, với mỗi lần thử, các bạn không cần in ra ~S(u)'~, mà chỉ cần in ra độ chênh lệch giữa hai giá trị cũ và mới, nói cách khác in ra ~S(u) - S(u)'~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 3 \times 10^5)~
• ~n-1~ dòng sau, 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 10^6)~ miêu tả cạnh thứ ~i~ của cây.

Output:

• Gồm một dòng gồm ~n~ số nguyên, số thứ ~i~ là ~S(i)~ nhỏ nhất thu được nếu ta thử gán tối ưu nhất có thể.

Subtask:

• Subtask ~1~ (~20\%~ số điểm): ~n \le 200~.
• Subtask ~2~ (~20\%~ số điểm): ~u_i = i, v_i = i+1~ ~\forall i \in [1,n-1]~.
• Subtask ~3~ (~20\%~ số điểm): ~w_i = 1~ với mọi ~i~ và ~n \le 2000~.
• Subtask ~4~ (~20\%~ số điểm): ~w_i = 1~ với mọi ~i~.
• Subtask ~5~ (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

6 8 6 6 30 15

Explanation 1

Đối với đỉnh ~1~, giả sử ta gán cạnh ~(3,5) = 0~, ta sẽ giảm được ~S(1)~ đi một lượng là ~6~ của ~D(5,1)~.

Đối với đỉnh ~2~, giả sử ta gán cạnh ~(1,2) = 0~, ta sẽ giảm được ~S(2)~ đi một lượng là ~8~.

Với đỉnh ~5~, cách gán tối ưu nhất là gán ~(3,5) = 0~.

Với đỉnh ~6~, ta gán ~(2,6) = 0~ để thu được kết quả là giảm đi ~15~ đơn vị.