Cho dãy ~A~ gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~.

Yêu cầu: Tìm số nguyên dương ~m~ nhỏ nhất không có mặt trong dãy ~A~.

Input

• Dòng đầu gồm số nguyên dương ~n~, ~n \le 10^5~.

• Dòng tiếp theo gồm ~n~ số nguyên dương không vượt quá ~10^9~.

  Output

• Số ~m~ tìm được.

Sample Input 1

5
6 1 3 2 4

Sample Output 1

5

Explanation 1

• Số nguyên dương nhỏ nhất không có mặt trong dãy là ~5~.

Yakumo Ran rất thích làm toán, hôm nay cô nghiên cứu bài toán sau:

Cho một mảng ~a~ có ~n~ phần tử, cho ~q~ truy vấn dạng l r x, hãy đếm số lượng số có giá trị ~x~ trong đoạn ~a[l...r]~.

Hiện tại cô chưa có lời giải cho bài toán này nên nhờ các bạn giúp!

Input

• Dòng đầu tiên gồm hai số tự nhiên ~n, q \le 10^5~.
• Dòng tiếp theo là mảng ~a~ nguyên với ~1 \le a_i \le 10^9~.
• ~q~ dòng tiếp theo mỗi dòng gồm 3 số ~l_i, r_i, x_i~ là truy vấn thứ ~i~.

Output

• Với mỗi truy vấn in ra kết quả.

Sample Test

Input:

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

Output:

2
1

Với hai số nguyên dương ~u,v~, khi viết số ~v~ sau số ~u~ ta được một số mới.

Ví dụ: ~u = 99, v = 123~, khi viết số ~v~ sau ~u~ ta thu được số mới là số ~99123~.

Cho ~n~ số nguyên dương ~a_1, a_2, a_3, ... a_n~ và ~m~ số nguyên dương ~b_1, b_2, b_3, ..., b_m~.

Yêu cầu:

• Với mỗi giá trị ~b_i~ ~(1 \le i \le m)~, bạn hãy cho biết có bao nhiêu số ~a_j~ (~1 \le j \le n~) sao cho sau khi viết ~a_j~ sau ~b_i~ ta được một số mới chia hết cho ~3~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,m~. (~1 \le n,m \le 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương miêu tả dãy ~a~. (~a_i \le 10^8, 1 \le i \le n~).
• Dòng tiếp theo chứa ~m~ số nguyên dương miêu tả dãy ~b~. (~b_i \le 10^8, 1 \le i \le m~).

Output

• Gồm ~m~ dòng, dòng thứ ~i~ ghi số lượng số ~a_j (1 \le j \le n)~ sao cho sau khi viết ~a_j~ sau ~b_i~ ta được một số mới chia hết cho ~3~.

Subtask

• Subtask ~1~ (~60\%~ số điểm): ~n,m \le 1000~
• Subtask ~2~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

5  2
123  4  5  7  10
3  2

Sample Output 1

1
3

Explanation 1

~b_1 = 3~ chỉ có duy nhất một số ~a_1~ thỏa mãn. ~b_2 = 2~, có ba số ~a_2,a_4,a_5~ thỏa mãn.

Bé Tommy rất thích tìm hiểu về các số đặc biệt, hôm trước trong giờ học lập trình thầy giáo dạy cho bé về số hoàn hảo (số hoàn hảo là số có tổng các ước (không kể nó) bằng chính nó, ví dụ số ~6~ là số hoàn hảo vì ~6=1+2+3~), bé cảm thấy hứng thú với con số này. Về nhà bé nghĩ ra khá nhiều bài toán xử lí số hoàn hảo. Nhưng hôm nay, thầy cho bé một bài tập rất hóc búa, nghĩ mãi không ra cách làm tốt nhất để được tối đa điểm của bài, nên bé nhờ các bạn học sinh giỏi làm giúp. Bài toán như sau:

Cho dãy ~a_1,a_2,…,a_n~ , ban đầu tất cả các phần tử có giá trị bằng ~0~. Có ~m~ phép biến đổi dạng ~(u,v,k)~: tăng giá trị các phần tử từ vị trí ~u~ đến vị trí ~v~ lên ~k~ đơn vị. Dữ liệu đảm bảo sau ~m~ phép biến đổi ~0<a_i \le 10^6~ ~(\forall i=1..n)~ và có ít nhất một số hoàn hảo trong dãy. </p>

Yêu cầu:

• Với dãy ~a_1,a_2,…,a_n~ sau ~m~ phép biến đổi, thầy yêu cầu đưa ra vị trí các số hoàn hảo theo thứ tự tăng dần.

Input

• Dòng đầu là hai số nguyên dương ~n,m~ tương ứng là số phần tử của dãy và số lượng phép biến đổi;
• ~m~ dòng sau mỗi dòng là ba số nguyên dương ~u,v,k~ ~(0 < u \le v \le n)~.

Output

• In ra các dòng, mỗi dòng chứa một số nguyên dương là vị trí của số hoàn hảo tìm được trong dãy theo thứ tự tăng dần.

Subtask

• Subtask ~1~ (~35\%~ số điểm): ~ 1 \le n,m \le 10^2~
• Subtask ~2~ (~35\%~ số điểm): ~n \le 10^5, m \le 10^3~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 10^5, m \le 10^5~

Sample Input 1

6 3
1 6 6
2 3 4
3 5 22

Sample Output

1
4
5
6

Explanation 1

• Dãy thu được sau ~3~ phép biến đổi là: 6 10 32 28 28 6

Hôm nay Sủi shop được ~n~ bài để cho vào chên ninh contest. Mỗi bài có 2 chỉ số ~a_i~ là chủ đề của bài và ~b_i~ là độ khó, tất cả các bài đều khác nhau, nghĩa là không có 2 bài bất kì nào đều có cùng chủ đề và độ khó. Sủi cần chọn ra 3 bài thỏa mãn ít nhất 1 trong 2 điều kiện sau:

• Chủ đề của 3 bài khác nhau.
• Độ khó của 3 bài khác nhau.

Hãy đếm số cách để Sủi có thể chọn ra 3 bài như vậy.

Input

• Dòng đầu tiên gồm số nguyên không âm ~3 \le n \le 10^5~.
• ~n~ dòng tiếp theo mỗi dòng gồm 2 số ~1 \le a_i, b_i \le n~.

Output

• Hãy in ra số cách chọn.

Sample Test

Input:

4
2 4
3 4
2 1
1 3

Output:

3

Input:

5
1 5
2 4
3 3
4 2
5 1

Output:

10

Người thầy quốc dân Gojo Satoru giờ đang có một niềm đam mê với tin học. Để lan tỏa điều này, anh muốn đố các học sinh của mình một bài toán như sau: Cho một dãy số nguyên ~a~ gồm ~n~ phần tử, định nghĩa ~f(l,r)~ là ~max(a_i) - min(a_i) \forall (l \le i \le r)~.

Hãy tính tổng của ~f(l,r) \forall (1 \le l \le r \le n)~.

Tất nhiên, do bận đi làm nhiệm vụ, các học sinh của thầy không rảnh để giải bài toán này, hãy thử giải nó giúp họ nhé.

Input:

• Dòng đầu gồm số nguyên dương ~n~. ~(1 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên miêu tả dãy ~a~. ~(|a_i| \le 10^6)~.

Output:

• Ghi ra một số nguyên miêu tả kết quả của bài toán.

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Test

Input:

3
1 2 3

Output:

4

Giải thích:

Ta có ~f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 0 + 1 + 2 + 0 + 1 +0 = 4~.