Cho dãy ~a~ gồm ~n~ phần tử.

Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn có dạng ~(l,r,k)~, hãy in ra giá trị nhỏ thứ ~k~ của dãy ~a[l...r]~ ~(1 \le l \le r \le n; 1 \le k \le r-l+1)~.

Input

• Dòng đầu gồm hai số nguyên dương ~n~ và ~q~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~.
• ~q~ dòng sau, mỗi dòng gồm ba số nguyên ~(l,r,k)~ biểu thị truy vấn.

Constraints

• ~1 \le n,q \le 2 \times 10^5~.
• ~1 \le a_i \le 10^9~.

Output

• Với mỗi truy vấn, in ra kết quả tương ứng.

Sample Input 1

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

Sample Output 1

3
1
3

Trường HNAMS gồm ~n~ học sinh, hầu hết mọi người đều có quan hệ tốt với nhau, tuy nhiên hiện tại vẫn còn ~m~ mối quan hệ "toxic", được biểu diễn dưới dạng ~(u_i,v_i)~ - tức là nếu hai người ~u_i~ và ~v_i~ chung nhóm, họ sẽ không hài lòng, và độ tức giận sẽ là ~i~.

Trường HNAMS muốn tổ chức School Building cho học sinh, đồng nghĩa với việc cần chia học sinh ra làm hai nhóm. Điều này sẽ làm một số mối quan hệ "toxic" chung nhóm, và độ tức giận của một cách chia sẽ là độ "toxic" lớn nhất trong các mối quan hệ xấu bị chung nhóm.

Trước giờ ~G~, ~mrtee~ nhận được chỉ thị rằng cần tính ~q~ giả định, giả định thứ ~i~ có dạng như sau:

• ~(a_i,b_i)~, tức là, nếu bắt buộc phải chia nhóm sao cho học sinh ~a_i~ và ~b_i~ khác nhóm nhau, thì độ tức giận nhỏ nhất có thể sẽ là bao nhiêu?

Hãy giúp ~mrtee~ trả lời các giả định nhé!

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, m, q~.
• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u_i~ và ~v_i~ ~(u_i \neq v_i, u_i, v_i \leq n)~ biểu diễn mối quan hệ toxic thứ ~i~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a_i~ và ~b_i~ ~(a_i \neq b_i, a_i, b_i \leq n)~ biểu diễn giả định thứ ~i~.

Output

• Với mỗi truy vấn, in ra đáp án tương ưng trên một dòng. Nếu có cách chia để không động tới mối quan hệ toxic nào, đáp án là ~0~.

Subtask

• Subtask 1 (~50\%~ số điểm): ~n, m, q \leq 2000~.
• Subtask 2 (~50\%~ số điểm): ~n, m, q \leq 5 \times 10^{5}~.

Sample Input 1

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

Sample Output 1

0
2
1

Cho dãy ~a~ gồm ~n~ phần tử.

Bạn cần thực hiện ~q~ truy vấn, mỗi truy vấn sẽ ở một trong hai dạng sau:

• Loại ~1~: ~(1,i,v)~, gán ~a_i = v~.
• Loại ~2~: ~(2,l,r,k)~, hãy in ra giá trị nhỏ thứ ~k~ của dãy ~a[l...r]~ ~(1 \le l \le r \le n; 1 \le k \le r-l+1)~.

Input

• Dòng đầu gồm hai số nguyên dương ~n~ và ~q~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~.
• ~q~ dòng sau, mỗi dòng miêu tả một truy vấn thuộc một trong hai loại:
  • Loại ~1~: ~(1,i,v)~.
  • Loại ~2~: ~(2,l,r,k)~.

Constraints

• ~1 \le n,q \le 2 \times 10^5~.
• ~1 \le a_i \le 10^9~.

Output

• Với mỗi truy vấn loại ~2~, in ra kết quả tương ứng.

Sample Input 1

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

Sample Output 1

3
3
5

Có ~n~ chiếc lá nằm liên tiếp từ vị trí ~1~ tới ~n~ trên một tuyến đường thẳng. Chiếc lá thứ ~i~ có tọa độ là ~i~.

Bạn quyết định hôm nay là một ngày đẹp trời để dọn dẹp, và bạn sẽ gom ~n~ chiếc lá thành ~k~ đống. Do lười, bạn sẽ đi từ cuối vườn về (ở tọa độ ~n~ về tọa độ ~1~) để thực hiện gom lá, do đó bạn chỉ có thể gom các lá về phía bên trái.

Chi phí di chuyển một chiếc lá bằng tích của trọng lượng chiếc lá và khoảng cách di chuyển. Tất nhiên, một trong ~k~ đống lá sẽ nằm ở vị trí ~1~, còn lại thì nó có thể nằm ở bất cứ đâu.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,k~ ~(n \le 10^5; k \le 10)~ miêu tả số chiếc là và số đống cần gom.
• Dòng thứ hai gồm ~n~ số nguyên dương, số thứ ~i~ miêu tả trọng lượng của chiếc là thứ ~i~. Trọng lượng của các chiếc là không vượt quá ~10^6~.

Output

• In ra chi phí nhỏ nhất để gom ~n~ chiếc lá lại thành đúng ~k~ đống.

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

6

Cho dãy số nguyên dương ~𝐴~ có ~𝑁~ phần tử ~𝑎_1, 𝑎_2, … , 𝑎_N~. Có ~𝑄~ truy vấn có dạng ~𝐿, 𝑅, 𝐾~ với ý nghĩa như sau:

• Xét dãy con ~𝐵~ là dãy con của ~𝐴~ gồm các phần tử liên tiếp từ vị trí ~𝐿~ đến vị trí ~𝑅~ : ~𝑎_L, 𝑎_{L+1}, … , a_R~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~, ta xây dựng dãy số ~𝐶~ bằng cách coi ~𝐶~ là tập hợp tất cả các dãy con liên tiếp của ~B~. Ví dụ: dãy ~𝐵 = \{1, 2, 1\}~ các dãy con của ~B~ là ~\{1\}, \{2\}, \{1\}, \{1,2\}, \{2,1\}, \{1,2,1\}~ ta sẽ có dãy ~𝐶 = \{1, 2, 1, 1, 2, 2,1, 1,~~ 2, 1\};~
• Sắp xếp dãy ~𝐶~ theo thứ tự không giảm và đưa ra phần tử thứ ~𝐾~. Ví dụ: với dãy ~𝐶~ trên ta sắp xếp thành ~\{1, 1, 1, 1, 1, 1, 2, 2, 2, 2\}~ và phần tử thứ ~8~ là ~2~.

Yêu cầu: Cho dãy số ~𝐴~ và ~𝑄~ truy vấn như trên, hãy đưa ra kết quả phần tử thứ ~𝐾~ của dãy số ~𝐶~ tương ứng trong mỗi truy vấn.

Dữ liệu nhập vào từ file văn bản DLT.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~𝑁~ và ~𝑄~ ~(1 ≤ 𝑁, 𝑄 ≤ 5 \times 10^5)~ là số phần tử của dãy số ~𝐴~ và số lượng truy vấn~;~
• Dòng thứ hai gồm ~𝑁~ số nguyên dương ~𝑎_1, 𝑎_2, … , 𝑎_N~ ~(1 ≤ 𝑎_i ≤ 5 \times 10^5; \ 1 ≤ 𝑖 ≤ 𝑁);~
• ~𝑄~ dòng sau, mỗi dòng chứa ba số ~𝐿, 𝑅, 𝐾~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~ mô tả truy vấn.

Dữ liệu đảm bảo đúng đắn, luôn có kết quả.

Kết quả ghi ra file văn bản DLT.OUT:

~𝑄~ dòng là kết quả tương ứng của mỗi truy vấn.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 100;~
• ~10\%~ số test khác ứng với ~10\%~ số điểm của bài thoả mãn: ~𝑁, 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 5000;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 10^5; 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 10^5;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 2
1 2 1 3 2
1 3 8
1 4 18

Output

2
3