Cho hai đồ thị vô hướng có trọng số, mỗi đồ thị có ~n~ đỉnh. Đồ thị thứ nhất có ~m_1~ cạnh, đồ thị thứ hai có ~m_2~ cạnh. Ngoài ra, đỉnh ~i~ ở đồ thị thứ nhất được nối với đỉnh ~i~ ở đồ thị thứ hai bằng một cạnh có trọng số ~x~ (với mọi ~i~ từ ~1~ đến ~n~).

Tìm đường đi ngắn nhất từ đỉnh ~s~ của đồ thị thứ nhất đến đỉnh ~t~ của đồ thị thứ hai.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~x~ — số đỉnh mỗi đồ thị và trọng số cạnh nối giữa hai đồ thị (~1 \le n \le 10^5~; ~1 \le x \le 10^6~).
• Dòng tiếp theo chứa số nguyên ~m_1~ — số cạnh của đồ thị thứ nhất (~0 \le m_1 \le 10^6~).
• ~m_1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i~, ~v_i~, ~c_i~ — cạnh nối đỉnh ~u_i~ với ~v_i~ có trọng số ~c_i~ trong đồ thị thứ nhất (~1 \le u_i, v_i \le n~; ~1 \le c_i \le 10^6~).
• Tiếp theo là thông tin đồ thị thứ hai theo cùng định dạng: dòng đầu chứa ~m_2~, sau đó là ~m_2~ dòng mô tả cạnh.
• Dòng cuối cùng chứa hai số nguyên ~s~ và ~t~ — đỉnh xuất phát ở đồ thị thứ nhất và đỉnh đích ở đồ thị thứ hai (~1 \le s, t \le n~).

Dữ liệu ra

In ra một số nguyên duy nhất — độ dài đường đi ngắn nhất, hoặc ~-1~ nếu không tồn tại đường đi.

Ví dụ

Dữ liệu

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

Kết quả

6

Tìm số nguyên ~m~ lớn nhất không vượt quá ~n~ sao cho ~m - 1~ chia hết cho mọi số nguyên từ ~1~ đến ~k~.

Nói cách khác, sau khi trừ đi ~1~ phần (dùng cho việc khác), phần còn lại ~m - 1~ phải chia đều được cho bất kỳ số người nào từ ~1~ đến ~k~, mỗi người nhận số phần bằng nhau và không có phần thừa. Cho phép mỗi người nhận ~0~ phần.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên ~n~ và ~k~ (~1 \le n, k \le 10^{18}~).

Dữ liệu ra

In ra số nguyên ~m~ — giá trị lớn nhất thỏa mãn điều kiện.

Ví dụ

Cho đồ thị vô hướng gồm ~n~ đỉnh và ~m~ cạnh. Mỗi đỉnh ~i~ có giá trị năng lượng ~a_i~. Mỗi cạnh nối đỉnh ~u_i~ với ~v_i~ và có ngưỡng năng lượng ~w_i~.

Ban đầu, bạn ở đỉnh ~s~ và mức năng lượng bằng ~0~. Khi đến thăm một đỉnh ~i~ lần đầu tiên, mức năng lượng tăng vĩnh viễn thêm ~a_i~. Bạn chỉ có thể đi qua cạnh có ngưỡng ~w_i~ nếu mức năng lượng hiện tại không nhỏ hơn ~w_i~.

Tìm mức năng lượng lớn nhất có thể đạt được khi xuất phát từ đỉnh ~s~.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~n~, ~m~, ~s~ — số đỉnh, số cạnh, đỉnh xuất phát (~1 \le s \le n \le 10^5~; ~1 \le m \le 2 \cdot 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ — giá trị năng lượng của mỗi đỉnh (~1 \le a_i \le 10^9~).
• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i~, ~v_i~, ~w_i~ — cạnh nối ~u_i~ với ~v_i~ có ngưỡng ~w_i~ (~1 \le u_i, v_i \le n~; ~0 \le w_i \le 10^9~).

Đồ thị không có cạnh bội hay khuyên, nhưng không nhất thiết liên thông.

Dữ liệu ra

In ra một số nguyên — mức năng lượng lớn nhất có thể đạt được.

Ví dụ

Cho số nguyên dương ~n~. Bạn cần đưa ra một chuỗi ~s~ gồm ~n~ ký tự là các chữ cái Latin thường từ ~a~ đến ~z~.

Sau khi nhận chuỗi, hệ thống thực hiện:

1. Đếm số lượng ký tự phân biệt trong ~s~, gọi là ~k~.
2. Gán cho mỗi ký tự xuất hiện trong ~s~ một trọng số là một số nguyên duy nhất từ ~1~ đến ~k~. Gọi trọng số của ký tự ~c~ là ~w(c)~.
3. Tính ~T = \sum_{c \in s} w(c)~ (tổng trọng số tất cả các ký tự trong chuỗi).

Hệ thống luôn gán trọng số sao cho ~T~ nhỏ nhất có thể. Hãy tìm chuỗi có độ dài ~n~ sao cho giá trị ~T~ (sau khi hệ thống tối ưu) là lớn nhất.

Dữ liệu vào

Một dòng chứa số nguyên ~n~ (~1 \le n \le 10^5~).

Dữ liệu ra

In ra chuỗi gồm ~n~ chữ cái Latin thường thỏa mãn yêu cầu. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ví dụ

Cho ~n~ hình chữ nhật, hình thứ ~i~ có kích thước ~h_i \times w_i~. Mỗi hình chữ nhật có thể được xoay ~90°~ (hoán đổi chiều cao và chiều rộng).

Hình chữ nhật kích thước ~(h_1, w_1)~ có thể lồng vào hình chữ nhật kích thước ~(h_2, w_2)~ nếu ~h_1 \le h_2~ và ~w_1 \le w_2~.

Tìm dãy hình chữ nhật dài nhất sao cho mỗi hình có thể lồng vào hình tiếp theo.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~).
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~h_i~ và ~w_i~ (~1 \le h_i, w_i \le 10^9~).

Dữ liệu ra

• Dòng đầu tiên in ra số lượng hình chữ nhật tối đa trong dãy.
• Dòng thứ hai in ra các chỉ số (đánh số từ ~1~) của các hình chữ nhật, theo thứ tự từ nhỏ nhất đến lớn nhất.

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ví dụ

Ghi chú

Ở ví dụ đầu, xoay hình chữ nhật thứ ~4~ thành ~(1, 4)~, ta được dãy ~(1,1), (1,4), (2,5), (3,5)~. Mỗi hình lồng được vào hình tiếp theo. Không thể tìm được dãy dài hơn.

Cho hình chữ nhật kích thước ~n \times m~. Hai người chơi lần lượt thực hiện tổng cộng ~2k~ lượt (mỗi người ~k~ lượt). Người thứ nhất đi trước.

Mỗi lượt, người chơi chọn một cạnh của hình chữ nhật và tăng nó thêm ~1~. Điểm nhận được bằng lượng thay đổi diện tích (tức bằng cạnh còn lại). Cả hai người chơi đều chơi tối ưu nhằm tối đa hóa điểm của mình.

Xác định người thắng và chênh lệch điểm.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 10^9~).
• Dòng thứ hai chứa số nguyên ~k~ — số lượt mỗi người (~1 \le k \le 10^9~).

Dữ liệu ra

In ra hai giá trị cách nhau bởi dấu cách:

• Nếu người thứ nhất thắng, in ~1~; nếu người thứ hai thắng, in ~2~; nếu hòa, in ~0~.
• Chênh lệch điểm (không âm) giữa người thắng và người thua.

Ví dụ

Cho bảng kích thước ~n \times m~, mỗi ô có màu đen (~1~) hoặc trắng (~0~). Bạn có thể thực hiện phép đảo màu tất cả các ô trên một hàng hoặc một cột (đen thành trắng và ngược lại).

Tìm số phép đảo ít nhất để tồn tại đường đi từ ô ~(1,1)~ đến ô ~(n,m)~ chỉ qua các ô đen, mỗi bước đi sang phải hoặc xuống dưới. Nếu không thể, in ~-1~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \le n, m \le 2000~).
• ~n~ dòng tiếp theo, mỗi dòng gồm ~m~ ký tự ~0~ hoặc ~1~.

Dữ liệu ra

Nếu không thể tạo đường đi, in ~-1~.

Ngược lại:

• Dòng đầu tiên in hai số nguyên ~r~ và ~c~ — số hàng và số cột được đảo.
• Dòng thứ hai in ~r~ số — chỉ số các hàng được đảo.
• Dòng thứ ba in ~c~ số — chỉ số các cột được đảo.

Hàng và cột đánh số từ ~1~. Trong các đáp án tối ưu (~r + c~ nhỏ nhất), in ra bất kỳ đáp án nào.

Ví dụ

Cho hai số ~n~ và ~k~. Mỗi xâu nhị phân ~t~ có độ dài ~k~ được gán giá trị ~d_t~. Với một xâu nhị phân ~s~ có độ dài ~n~, định nghĩa:

~\text{danger}(s) = \sum_{i=1}^{n-k+1} d_{s_i s_{i+1} \ldots s_{i+k-1}}~

Tìm xâu nhị phân ~s~ có độ dài ~n~ sao cho ~\text{danger}(s)~ nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le n \le 1000~; ~1 \le k \le 10~).
• Dòng thứ hai chứa ~2^k~ số nguyên — giá trị ~d_t~ cho tất cả các xâu nhị phân có độ dài ~k~ theo thứ tự từ điển (~1 \le d_t \le 1000~).

Dữ liệu ra

In ra xâu nhị phân có độ dài ~n~ với tổng giá trị nhỏ nhất. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ví dụ

Ghi chú

Ở ví dụ đầu, tổng giá trị bằng ~d_{10} + d_{01} + d_{10} + d_{01} + d_{10} + d_{01} = 3 \times (1 + 2) = 9~.

Ở ví dụ hai, tổng giá trị bằng ~d_{010} + d_{100} + d_{001} = 4 + 3 + 5 = 12~.

Cho đồ thị có hướng gồm ~n~ đỉnh. Mỗi đỉnh có đúng ~2~ cung đi ra và đúng ~2~ cung đi vào. Mỗi cung có ràng buộc ~[a_i, b_i]~ về giá trị ~w~.

Chọn đúng ~n~ cung sao cho chúng tạo thành một tập các chu trình phủ tất cả ~n~ đỉnh. Đồng thời, phải tồn tại giá trị ~w~ sao cho ~a_i \le w \le b_i~ trên mọi cung được chọn.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ (~3 \le n \le 10^5~).
• ~2n~ dòng tiếp theo mô tả các cung: cứ mỗi hai dòng liên tiếp là hai cung đi ra từ đỉnh ~1~, rồi hai cung từ đỉnh ~2~, v.v. Mỗi dòng chứa ba số nguyên ~t_i~, ~a_i~, ~b_i~ — đỉnh đích, cận dưới và cận trên của ~w~ (~1 \le t_i \le n~; ~1 \le a_i \le b_i \le 10^5~).

Mỗi đỉnh có đúng ~2~ cung đi vào. Không có khuyên, nhưng có thể có hai cung giữa cùng một cặp đỉnh.

Dữ liệu ra

Nếu không tồn tại phương án, in ~-1~.

Ngược lại:

• Dòng đầu tiên in giá trị ~w~.
• Dòng thứ hai in ~n~ số nguyên — chỉ số của các cung được chọn (đánh số từ ~1~ đến ~2n~ theo thứ tự đầu vào).

Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Ví dụ

Ghi chú

Ở ví dụ đầu, chọn cung ~1~ (~1 \to 2~, ~[1,3]~), cung ~3~ (~2 \to 3~, ~[2,4]~), cung ~5~ (~3 \to 1~, ~[3,5]~). Chu trình ~1 \to 2 \to 3 \to 1~ phủ mọi đỉnh, ~w = 3~.

Ở ví dụ hai, có hai chu trình ~1 \to 2 \to 5 \to 1~ và ~3 \to 4 \to 3~ với ~w = 6~.

Từ gốc tọa độ ~(0, 0)~, các tia sáng phát ra theo mọi hướng. Có ~n~ vật cản, mỗi vật cản là một hình tròn trên mặt phẳng, hấp thụ hoàn toàn mọi tia đi vào nó.

Xung quanh gốc tọa độ có một đường tròn lớn bán kính ~10^6~. Hãy tính tỉ lệ phần đường tròn lớn mà các tia sáng có thể chạm tới (không bị vật cản chặn).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~).
• ~n~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~x_i~, ~y_i~, ~r_i~ — tọa độ tâm và bán kính vật cản (~1 \le |x_i|, |y_i|, r_i \le 10^5~).

Các vật cản có thể chồng lên nhau.

Dữ liệu ra

In ra một số thực từ ~0~ đến ~1~ — tỉ lệ phần đường tròn lớn mà tia sáng chạm tới. Đáp án được chấp nhận nếu sai số không quá ~10^{-4}~.

Ví dụ

Ghi chú

Ở ví dụ đầu, tia sáng chỉ đi được đến nửa trái-trên và nửa phải-dưới, tức đúng một nửa đường tròn.

Cho cây gốc gồm ~n~ đỉnh, gốc là đỉnh ~1~. Mỗi đỉnh được gán nhãn ~A~ hoặc ~B~.

Định nghĩa độ bất đồng là số cặp ~(u, v)~ sao cho ~u~ là cha trực tiếp của ~v~, đỉnh ~u~ có nhãn ~A~ và đỉnh ~v~ có nhãn ~B~.

Tìm cách gán nhãn sao cho độ bất đồng là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^5~).
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_i~ và ~b_i~ — cạnh nối đỉnh ~a_i~ và ~b_i~ (~1 \le a_i, b_i \le n~). Không nhất thiết ~a_i~ là cha của ~b_i~.

Dữ liệu đảm bảo tạo thành cây.

Dữ liệu ra

• Dòng đầu tiên in hai số nguyên: giá trị bất đồng lớn nhất ~d~, và ~k~ — số đỉnh có nhãn ~A~.
• Dòng thứ hai in ~k~ số nguyên phân biệt — chỉ số các đỉnh có nhãn ~A~.

Nếu có nhiều đáp án tối ưu, in ra bất kỳ đáp án nào.

Ví dụ

Cho ~n~ nhân vật, mỗi nhân vật có ba tham số nguyên ~a_i~, ~b_i~, ~c_i~:

• ~a_i~: nếu ~a_i < 0~ thì nhân vật là lời nguyền, nếu ~a_i > 0~ thì là pháp sư, nếu ~a_i = 0~ thì là người thường.
• ~b_i~: nếu ~b_i < 0~ thì nhân vật hỗn loạn, nếu ~b_i > 0~ thì trật tự, nếu ~b_i = 0~ thì trung lập.
• ~c_i~: cấp độ sức mạnh.

Hãy chọn đúng ~k~ nhân vật sao cho tổng ~c_i~ đạt giá trị lớn nhất, đồng thời thỏa mãn hai ràng buộc sau:

1. Đội hình có nhiều nhất một nhân vật hỗn loạn (tức là ~b_i < 0~).
2. Đội hình không được đồng thời chứa cả lời nguyền lẫn pháp sư; nghĩa là toàn bộ đội hình phải gồm hoặc chỉ lời nguyền và người thường, hoặc chỉ pháp sư và người thường.

Đảm bảo luôn tồn tại ít nhất một đội hình hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ — tổng số nhân vật và số nhân vật cần chọn (~1 \le k \le n \le 2 \cdot 10^5~).

Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~a_i~, ~b_i~, ~c_i~ — các tham số của nhân vật thứ ~i~ (~-10^9 \le a_i, b_i \le 10^9~; ~1 \le c_i \le 10^9~).

Dữ liệu ra

In ra ~k~ số nguyên phân biệt từ ~1~ đến ~n~ theo thứ tự bất kỳ — chỉ số của các nhân vật trong đội hình tối ưu. Nếu có nhiều đáp án tối ưu, in ra một đáp án bất kỳ.

Ví dụ

Input 1

4 2
-1 1 5
0 1 4
2 1 6
0 -1 3

Output 1

3 2

Input 2

7 4
1 1 8
0 1 7
2 -1 10
-1 1 9
0 -1 6
-2 1 5
0 1 4

Output 2

1 2 7 3

Giải thích

Ví dụ 1: Chọn ~k = 2~ nhân vật. Nhân vật 3 là pháp sư (~a_3 = 2 > 0~), nhân vật 2 là người thường (~a_2 = 0~); cả hai đều không hỗn loạn. Tổng sức mạnh ~= 6 + 4 = 10~. Phương án chọn lời nguyền tốt nhất là nhân vật 1 và 2, tổng ~= 5 + 4 = 9 < 10~.

Ví dụ 2: Chọn nhân vật 1 (pháp sư, trật tự, sức 8), 2 (người thường, trật tự, sức 7), 3 (pháp sư, hỗn loạn, sức 10), 7 (người thường, trật tự, sức 4). Đội gồm toàn pháp sư/người thường, đúng một nhân vật hỗn loạn. Tổng sức mạnh ~= 10 + 8 + 7 + 4 = 29~.

Chấm điểm

Cho một đồ thị vô hướng ~n~ đỉnh, ~m~ cạnh, không có chu trình (tức là một rừng). Các đỉnh được đánh số từ ~1~ đến ~n~.

Cho ~q~ truy vấn, mỗi truy vấn cho một đoạn ~[l, r]~. Với mỗi truy vấn, hãy đếm số thành phần liên thông của đồ thị con gồm các đỉnh ~l, l+1, \ldots, r~ cùng toàn bộ cạnh có cả hai đầu mút thuộc ~[l, r]~.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ — số đỉnh và số cạnh (~0 \le m < n \le 5 \cdot 10^5~).

Trong ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i~ và ~v_i~ — hai đầu mút của cạnh thứ ~i~ (~1 \le u_i, v_i \le n~; ~u_i \ne v_i~).

Dòng tiếp theo chứa số nguyên ~q~ — số truy vấn (~1 \le q \le 2 \cdot 10^5~).

Trong ~q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~ và ~r_i~ — tham số truy vấn thứ ~i~ (~1 \le l_i \le r_i \le n~).

Đảm bảo đồ thị không có chu trình, không có khuyên và không có cạnh bội.

Dữ liệu ra

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Input 1

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

Output 1

1
2
2
2
1

Input 2

8 5
1 4
2 4
4 7
3 5
6 8
4
1 2
1 4
3 7
6 8

Output 2

2
2
3
2

Giải thích

Ví dụ 1: Đồ thị là đường thẳng ~1-2-3~ và ~4-5-6-7~.

• Truy vấn ~[1,3]~: cả 3 đỉnh nối thành một chuỗi ~1-2-3~, có 1 thành phần.
• Truy vấn ~[1,4]~: đỉnh 4 bị tách biệt, thành phần ~\{1,2,3\}~ và ~\{4\}~, có 2 thành phần.
• Truy vấn ~[5,7]~: chuỗi ~5-6-7~ liên thông, có 1 thành phần.

Ví dụ 2: Đồ thị có cạnh ~(1,4),\,(2,4),\,(4,7),\,(3,5),\,(6,8)~.

• Truy vấn ~[1,2]~: các cạnh liên quan đến 1 và 2 đều đi ra ngoài đoạn (qua đỉnh 4), không có cạnh nào nằm trong ~[1,2]~, nên có 2 thành phần.
• Truy vấn ~[3,7]~: cạnh ~(4,7)~ và ~(3,5)~ đều nằm trong ~[3,7]~, nên có ~5 - 2 = 3~ thành phần.

Ghi chú

Vì đồ thị là rừng (không chứa chu trình), số thành phần liên thông của đồ thị con ~[l,r]~ bằng:

$$\text{ans}(l,r) \;=\; (r - l + 1) \;-\; \bigl|\{(u,v)\in E \;:\; l \le \min(u,v) \text{ và } \max(u,v) \le r\}\bigr|$$

Chấm điểm

Ràng buộc về ~v_i, u_i, l_i, r_i~ trong bảng áp dụng cho mọi ~i~.

Cho ~m~ loại nhãn phân biệt, được đánh số từ ~0~ đến ~m-1~.

Một bùa chú kích thước ~n~ là một dãy gồm ~n~ nhãn phân biệt ~a_1, a_2, \ldots, a_n~, trong đó ~0 \le a_i < m~ với mọi ~i~.

Sức mạnh của bùa chú được định nghĩa là: $$f(a_1, \ldots, a_n) = \sum_{i=1}^{n} \text{mex}(a_1, \ldots, a_i)$$

Ở đây ~\text{mex}~ của một tập số là số nguyên không âm nhỏ nhất không thuộc tập đó.

Hãy tính tổng sức mạnh của tất cả các bùa chú phân biệt có thể tạo ra. Hai bùa chú ~a~ và ~a'~ được coi là khác nhau nếu tồn tại chỉ số ~1 \le i \le n~ sao cho ~a_i \ne a'_i~.

Vì kết quả có thể rất lớn, hãy in ra đáp án theo modulo ~10^9 + 7~.

Dữ liệu vào

Dòng duy nhất chứa hai số nguyên ~n~ và ~m~ — kích thước bùa chú và số loại nhãn (~1 \le n \le 10^6~; ~n \le m \le 10^9~).

Dữ liệu ra

In ra một số nguyên duy nhất — đáp án theo modulo ~10^9 + 7~.

Ví dụ

Input 1

2 3

Output 1

8

Input 2

3 5

Output 2

102

Input 3

100 100

Output 3

410874080

Giải thích

Ví dụ 1: ~n=2~, ~m=3~. Có ~P(3,2) = 6~ bùa chú phân biệt:

Tổng ~= 3+2+2+0+1+0 = 8~.

Chấm điểm

Cho mảng ~n~ số nguyên không âm ~a_1, \ldots, a_n~.

Khi đánh vào tường thứ ~i~ với lực ~x~:

• Nếu ~a_i \le x~: tường bị phá, lực giảm còn ~x - a_i~, rồi chuyển sang tường tiếp theo với lực ~x - a_i~.
• Nếu ~a_i > x~: tường không bị phá, lực giữ nguyên ~x~, rồi chuyển sang tường tiếp theo với lực ~x~.

Cho ~q~ truy vấn, mỗi truy vấn gồm ba số nguyên ~l~, ~r~, ~d~. Với mỗi truy vấn, hãy tìm lực cuối cùng lớn nhất có thể đạt được sau khi đi qua toàn bộ các tường ~a_l, a_{l+1}, \ldots, a_r~ theo thứ tự, biết rằng lực ban đầu là một số nguyên bất kỳ trong đoạn ~[0, d]~.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ — độ dài mảng và số truy vấn (~1 \le n, q \le 3 \cdot 10^5~).

Dòng thứ hai chứa ~n~ số nguyên ~a_i~ — các phần tử của mảng (~0 \le a_i \le 10^9~).

Trong ~q~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~l_i~, ~r_i~, ~d_i~ — tham số truy vấn thứ ~i~ (~1 \le l_i \le r_i \le n~; ~1 \le d_i \le 10^9~).

Dữ liệu ra

In ra ~q~ số nguyên, mỗi số trên một dòng — đáp án cho từng truy vấn theo thứ tự.

Ví dụ

Input 1

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

Output 1

2
1
3

Input 2

7 5
7 6 2 5 0 1 4
1 3 8
1 7 5
4 7 10
2 5 1
4 6 11

Output 2

3
2
3
1
5

Giải thích

Ví dụ 1:

• Truy vấn ~(5, 5, 3)~: chỉ có tường ~a_5 = 3~. Với ~x=3~: ~3 \le 3~, tường bị phá, lực còn ~0~. Với ~x=2~: ~3 > 2~, tường không bị phá, lực giữ nguyên ~2~. Đáp án ~= 2~.
• Truy vấn ~(1, 5, 4)~: với ~x=4~: ~0 \le 4 \to 4~; ~2 \le 4 \to 2~; ~6 > 2 \to 2~; ~1 \le 2 \to 1~; ~3 > 1 \to 1~. Đáp án ~= 1~.
• Truy vấn ~(1, 3, 5)~: với ~x=5~: ~0 \le 5 \to 5~; ~2 \le 5 \to 3~; ~6 > 3 \to 3~. Đáp án ~= 3~.

Ví dụ 2:

• Truy vấn ~(1, 3, 8)~: tường ~[7, 6, 2]~. Với ~x=5~: ~7 > 5 \to 5~; ~6 > 5 \to 5~; ~2 \le 5 \to 3~. Đáp án ~= 3~.
• Truy vấn ~(4, 6, 11)~: tường ~[5, 0, 1]~. Với ~x=11~: ~5 \le 11 \to 6~; ~0 \le 6 \to 6~; ~1 \le 6 \to 5~. Đáp án ~= 5~.

Chấm điểm