Mirko là một người đàn ông rất giản dị. Bạn của Mirko, Darko đã cho anh ta một mảng gồm \(N\) số nguyên dương và yêu cầu anh ta trả lời \(Q\) truy vấn liên quan đến mảng đã cho.

Mỗi truy vấn bao gồm hai số nguyên, thể hiện vị trí đầu và cuối của một đoạn trong mảng. Câu trả lời cho truy vấn ấy là số lượng các giá trị khác nhau xuất hiện đúng hai lần trong đoạn đã cho.

Input

• Dòng đầu tiên chứa số nguyên \(N\) và \(Q\) \((1 \leq N, Q \leq 500000)\).
• Dòng thứ hai chứa mảng gồm \(N\) số nguyên dương nhỏ hơn \(10^9\).
• \(Q\) dòng tiếp theo mỗi dòng chứa hai số nguyên \(L\) và \(R\) \((1 \leq L \leq R \leq N)\).

Output

• Hãy xuất ra \(Q\) dòng lần lượt là kết quả của \(Q\) truy vấn.

5 1
1 2 1 1 1
1 3

1

5 2
1 1 1 1 1
2 4
2 3

0
1

5 2
1 1 2 2 3
1 1
1 5

0
2

Cho dãy số nguyên \(a_1, a_2, ..., a_n\) và \(q\) truy vấn \((l, r, k)\) nghĩa là tìm số bé thứ \(k\) trong đoạn \((l, r)\). Hãy viết chương trình để làm nhiệm vụ bên trên.

Input

• Dòng đầu là hai số \(n\) và \(q\) \((n, q \le 10^5)\).
• Dòng thứ hai là dãy số nguyên \(a_1, a_2, ..., a_n\) \((a_n \le 10^9)\).
• \(q\) dòng tiếp theo, mỗi dòng là bộ ba số \((l, r, k)\) thể hiện một truy vấn \((1 \le l \le r \le n, 1 \le k \le r - l + 1)\).

Output

• \(q\) dòng là đáp án các truy vấn.

Example

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

5
6
3

Cho một tập các điểm trên mặt phẳng tọa độ Oxy, nhiệm vụ của bạn là tìm khoảng cách Euclid ngắn nhất giữa \(2\) điểm bất kì.

Một khoảng cách Euclid giữa \(2\) điểm \((x_1, y_1)\) và \((x_2, y_2)\) là \(\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\): số lượng điểm.
• Sau đó, bao gồm \(n\) dòng chứa thông tin về các điểm. Mỗi dòng chứa 2 số nguyên \(x\) và \(y\).
• Đề đảm bảo không tồn tại một cặp điểm bất kì trùng vị trí nhau.

Output

• In ra một số nguyên duy nhất là \(d^2\) trong đó \(d\) là khoảng cách Euclid ngắn nhất (để đảm bảo rằng kết quả chắc chắn là một số nguyên).

Constraints

• \(2 \leq n \leq 2 \cdot 10^5\)
• \(-10^9 \leq x, y \leq 10^9\)

Example

4
2 1
4 4
1 2
6 3

2

Cho dãy gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Hiệp đố Đức Anh tính số cách chọn ra một dãy con (không cần liên tiếp) có tổng bằng \(k\) trong dãy trên, Đức Anh khôn nên giải trong đúng \(36\) giây. Hiệp lại tăng độ khó, Hiệp hỏi \(q\) truy vấn \(l, r, k\) với ý nghĩa tính số cách chọn một dãy con có tổng bằng \(k\) trong dãy \(a_l, a_{l + 1}, \ldots, a_r\). Đức Anh gà nên nhờ bạn giúp, hãy giúp anh ấy.

Input

• Dòng đầu là hai số nguyên dương \(n\) và \(q\) \((1 \le n, q \le 10^5)\).
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((0 \le a_i \le 100)\).
• \(q\) dòng tiếp theo, mỗi dòng là ba số nguyên dương \(l, r, k\) thể hiện một truy vấn \((1 \le l \le r \le n, k \le 100)\).

Output

• \(q\) dòng là đáp án cho \(q\) truy vấn, lấy dư cho \(10^9 + 7\).

Example

5 3
1 9 8 1 2
1 5 2
1 4 10
1 5 3

2
3
2