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~.

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ài toán tìm ước chung lớn nhất và tìm bội chung nhỏ nhất của 2 số nguyên dương là bài toán quen thuộc khi học số học lớp 6. Cho biết ~M~ là ước chung lớn nhất ~2~ số nguyên dương, ~N~ là bội chung nhỏ nhất của ~2~ số nguyên dương.

Yêu cầu: Tìm ~2~ số nguyên dương ~a~ và ~b~ có tổng nhỏ nhất sao cho ước chung lớn nhất của ~a~ và ~b~ bằng ~M~, bội chung nhỏ nhất của ~a~ và ~b~ bằng ~N~.

Input

• Gồm một dòng duy nhất là hai số nguyên dương ~M~ và ~N~ (~1 \le N \le M \le 10^6)~.

Output

• Gồm một dòng duy nhất là hai số nguyên dương ~a~ và ~b~ ~(a \le b)~.

Sample Tests

Input

4 60

Output

12 20

Từ dãy số tự nhiên ~1; 2; 3; ...; N~ người ta sắp xêp lại dãy số này theo số dư trong các phép chia các số hạng của dãy số cho một số lự nhiên ~K~ là ước nào đó của ~N~ như sau:

• Đoạn thứ nhất gồm tất cả các số chia hết cho ~K~;
• Đoạn thứ hai gồm tất cả các sổ chia ~K~ dư 1;
• Đoạn thứ ba gồm tất cả các số chia ~K~ dư 2;
• ...
• Đoạn cuối cùng gồm tất cà các số chia ~K~ dư ~K~ - 1.

Các số hạng trong mỗi đoạn cũng được sắp xếp theo chiêu tăng dần.

Ví dụ: Với ~N = 12~ và ~K = 4~ sau khi sắp xếp ta có dãy số sau: ~4; 8; 12; 1; 5; 9; 2; 6; 10; 3; 7; 11~

Yêu cầu: Cho trước 3 số nguyên dương ~N; K; M~ (với ~K~ là ước của ~N~ và ~M < N~). Tìm số hạng thử ~M~ của dãy đã sắp xếp.

Input

• 3 số nguyên dương ~N; K; M~ (~N \le 10^{16}; K \le 10^9; K~ là ước của ~N~; ~M < N~) trên cùng một dòng, mỗi số cách nhau một dấu cách.

Output

• Ghi ra số hạng thứ M của dãy số theo yêu cầu.

Scoring

• Có 20% test ứng với ~N \le 10^2~;
• Có 30% test ứng với ~10^2 < N \le 10^6~;
• Có 30% test ứng với ~10^6 < N \le 10^9~;
• Có 20% test ứng với ~10^9 < N \le 10^{16}~.

Sample Tests

Input

12 4 6

Output

9

Cho dãy ~a~ nguyên dương gồm ~n~ phần tử. Ta định nghĩa hàm ~f(l,r)~ như sau: ~f(l,r) = 1\times a[l] + 2\times a[l+1] + 3\times a[l+2] + ... (r-l+1)\times a[r]~.

Có ~q~ truy vấn, mỗi truy vấn gồm hai số ~l~, ~r~ với ~1 \le l \le r \le n~. Với mỗi truy vấn, hãy in ra ~f(l,r)~.

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~q~. ~(1 \le n, q \le 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~l~, ~r~ miêu tả các truy vấn.

Ouput

• In ra ~q~ dòng, mỗi dòng là kết quả của một truy vấn tương ứng.

Subtask

• Subtask ~1~: ~n,q \le 2 \times 10^3~ ~(30\%)~
• Subtask ~2~: Trong tất cả các truy vấn, ~l=1~.
• Subtask ~3~: Không giới hạn gì thêm ~(40\%)~.

Sample Test

Input

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

Output

5
8
30

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

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

Cho một bảng hình chữ nhật có ~N~ dòng và ~M~ cột gồm các chữ cái in thường từ ~'a'~ đến ~'z'~. Bảng này có tính chất: ở mỗi cột, khi ghép các kí tự từ trên xuống dưới sẽ thu được một xâu đại diện và trong bảng các xâu đại diện là đôi một khác nhau.

Yêu cầu: Hãy tìm cách xoá nhiều nhất các dòng (lần lượt từ dòng đầu tiên xuống dưới) của bảng để thu được một bảng mới vẫn đảm bảo tính chất trên. (Chỉ được xoá tối đa ~N-1~ dòng)

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

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ cách nhau một dấu cách~;~
• ~N~ dòng sau, mỗi dòng chứa một xâu có dộ dài ~M.~

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

Gồm một số duy nhất là kết quả của bài toán.

Ví dụ

Input

5 4
qwpt
abcf
bvoa
abka
bbhb

Output

2

Giải thích:

Xoá tối đa ~2~ dòng đầu. Nếu xoá cả dòng thứ ~3~ thì cột đầu tiên và cột cuối cùng sẽ giống nhau. (không thoả mãn tính chất của bảng)

Giới hạn

• Có ~40\%~ số test tương ứng với số điểm có ~N,M≤100;~
• ~30\%~ số test khác tương ứng với số điểm có ~N,M≤500;~
• ~30\%~ số test còn lại tương ứng với số điểm có ~N,M≤5000.~

Trong cuộc thám hiểm gần đây, bạn đã phát hiện ra một hầm kho báu có thể được biểu diễn dưới dạng lưới với ~N~ hàng (được đánh số từ ~1~ đến ~N~) và ~M~ cột (được đánh số từ ~1~ đến ~M~). Ô ở hàng ~r~ và cột ~c~ được ký hiệu là ~(r, c)~. Ô ~(r, c)~ chứa kho báu nếu ~A_{r,c} = 1~, và ô đó trống nếu ~A_{r,c} = 0~.

Có ~Q~ kịch bản độc lập. Đối với mỗi kịch bản, bạn bắt đầu ở ô ~(R, C)~ và bạn muốn mang chính xác ~K~ kho báu trở về ô ~(R, C)~. Trong một giây, bạn có thể di chuyển đến bất kỳ ô nào kề bên theo hướng ngang, dọc hoặc chéo với ô bạn đang đứng, như được minh họa trong hình dưới đây. Do kho báu rất lớn, bạn chỉ có thể mang mỗi lần một kho báu, nghĩa là bạn phải mang kho báu trở về ô ~(R, C)~ trước khi lấy kho báu tiếp theo hoặc để hoàn thành kịch bản. Hành động nhặt hoặc bỏ kho báu không tốn thời gian.

Đối với mỗi kịch bản, xác định thời gian tối thiểu cần thiết (tính bằng giây) để mang ~K~ kho báu về ô ~(R, C)~ nếu bạn bắt đầu ở ô ~(R, C)~. Vì tất cả các kịch bản đều độc lập với nhau, nên sau mỗi kịch bản, các kho báu sẽ được trở lại vị trí ban đầu.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~M~ (~1 \leq N, M \leq 1000~).
• Mỗi dòng trong ~N~ dòng tiếp theo bao gồm một chuỗi nhị phân ~A_i~ có độ dài ~M~. Ký tự thứ ~j~ của chuỗi ~A_i~ mô tả ô ~(i, j)~: là ~1~ nếu ô ~(i, j)~ chứa kho báu và là ~0~ nếu ô ~(i, j)~ trống. Số lượng kho báu trong hầm ít nhất là một.
• Dòng tiếp theo chứa một số nguyên ~Q~ (~1 \leq Q \leq 2 \times 10^4~).
• Mỗi dòng trong ~Q~ dòng tiếp theo gồm ba số nguyên ~R~, ~C~ và ~K~ (~1 \leq R \leq N~; ~1 \leq C \leq M~; ~1 \leq K~) mô tả mỗi kịch bản. Giá trị của ~K~ không vượt quá số lượng kho báu trong hầm.

Output

• Đối với mỗi kịch bản, xuất ra một số nguyên trên một dòng riêng biệt biểu thị thời gian tối thiểu (tính bằng giây) để mang ~K~ kho báu về ô ~(R, C)~ nếu bạn bắt đầu ở ô ~(R, C)~.

Sample

Input 1

5 5
11000
01011
10111
00101
10010
6
1 1 1
1 2 4
3 1 13
1 4 5
2 5 3
3 3 8

Output 1

0
8
64
16
4
20

Input 2

1 6
000111
3
1 1 2 
1 1 1
1 6 3

Output 2

14
6
6