Cho mảng \(A\) gồm \(N\) phần tử. Bạn cần thực hiện \(Q\) truy vấn: với mỗi truy vấn, tìm giá trị ở phân vị (percentile) thứ \(P\) (\(1 \le P \le 100\)) của đoạn con từ vị trí \(L\) đến \(R\) (1-indexed).

Ở đây, phân vị thứ \(P\) của một đoạn con có độ dài \(len\) được định nghĩa là phần tử nhỏ thứ \(K\) của đoạn con đó sau khi sắp xếp tăng dần, với: \[K = \max\left(1, \left\lceil \frac{len \times P}{100} \right\rceil\right)\]

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(L\), \(R\) và \(P\) (\(1 \le L \le R \le N, 1 \le P \le 100\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra giá trị phân vị tìm được trên một dòng.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000\).
• Subtask 2 (70% số điểm): \(N, Q \le 10^5\), các ràng buộc gốc.

Ví dụ

Input:

5 3
4 2 7 1 5
1 3 50
2 5 25
1 5 100

Output:

4
2
7

Giải thích:

• Truy vấn 1: Đoạn \([1..3]\) là \([4, 2, 7]\), độ dài 3, \(P = 50\). \(K = \lceil \frac{3 \times 50}{100} \rceil = 2\). Phần tử nhỏ thứ 2 là 4.
• Truy vấn 2: Đoạn \([2..5]\) là \([2, 7, 1, 5]\), độ dài 4, \(P = 25\). \(K = \lceil \frac{4 \times 25}{100} \rceil = 1\). Phần tử nhỏ thứ 1 là 1? Khoan, ví dụ đầu ra là 2? Để xem: mảng con \([2, 7, 1, 5]\) sắp xếp là \([1, 2, 5, 7]\). Nếu \(K=1\), thì là 1. Tại sao ví dụ ra 2? À! Vị trí của mảng \(A\) là 1-indexed. \(A = [4, 2, 7, 1, 5]\). Đoạn \([2..5]\) chứa các phần tử \(A_2, A_3, A_4, A_5\) là \([2, 7, 1, 5]\). Nếu \(K = 1\), phần tử nhỏ thứ 1 là 1. Hãy sửa ví dụ đầu ra thành: 4 1 7 Và giải thích:
  • Truy vấn 2: Đoạn \([2..5]\) là \([2, 7, 1, 5]\), sắp xếp: \([1, 2, 5, 7]\). \(K = 1 \to\) kết quả 1.
  • Truy vấn 3: Đoạn \([1..5]\), \(P=100 \to K = 5 \to\) phần tử nhỏ thứ 5 (lớn nhất) là 7.