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

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

Nam được mẹ giao nhiệm vụ rèn luyện phép tính cộng cho em trai. Nam dự định vừa rèn luyện tính cộng vừa tạo niềm yêu thích tin học bằng cách cho em trai giải bài toán sau:

Cho một bảng số nguyên gồm có ~m~ hàng và ~n~ cột. Các hàng của bảng được đánh số từ ~1~ tới ~m~ từ trên xuông dưới, các cột của bảng số được đánh số từ ~1~ tới ~n~ từ trái qua phải. Giá trị của số nằm ở hàng ~i~ cột ~j~ được kí hiệu là ~a(i,j)~. Cần thực hiện lần lượt ~Q~ thao tác, thao tác thứ ~t~ ~(1 \le t \le Q)~ được mô tả bằng bộ năm số ~x_t,y_t,u_t,v_t,c_t~, thao tác này sẽ tăng tất cả các phần tử ~a(i,j)~ với mọi ~x_i \le i \le u_t, y_t \le j \le v_t~ lên một lượng là ~c_t~ ~(c_t > 0)~.

Nam sẽ yêu cầu em trai ghi ra giấy tất cả các phần tử của bảng số sau khi đã thực hiện cả ~Q~ thao tác. Để kiểm tra xem em mình làm có đúng không, Nam phải tự mình tính toán ra được kết quả đúng trước đã. Sau một hồi tính toán, Nam đã có được bảng số sau khi thực hiện ~Q~ thao tác. Tuy nhiên, giá trị của các phần tử của bảng số kết quả khá lớn! Nam sợ rằng em trai mình sẽ gặp khó khăn khi thực hiện phép cộng giữa hai số lớn, do đó Nam quyết định bỏ đi một thao tác sao cho sau khi thực hiện ~Q-1~ thao tác còn lại, giá trị lớn nhất của bảng số là nhỏ nhất có thể.

Yêu cầu: Cho bảng số và dãy ~Q~ thao tác, gọi ~W_t~ là giá trị lớn nhất trong bảng sau khi bỏ đi thao tác thứ ~t~ ~(1 \le t \le Q)~, tính ~Min(\{W_1,W_2,...,W_Q\})~.

Input

• Dòng đầu chứa hai số nguyên dương ~n,m~ .
• ~n~ dòng sau, dòng thứ ~i~ gồm ~n~ số nguyên không âm ~a(i,1), a(i,2), ..., a(i,n)~.
• Dòng tiếp theo chứa số nguyên dương ~Q~.
• Tiếp theo là ~Q~ dòng, dòng thứ ~t~ gồm ~5~ số nguyên dương ~x_t,y_t,u_t,v_t,c_t~.

Điều kiện

• ~1 \le n \times m \le 10^6~
• ~1 \le Q \le 10^6~
• ~a(i,j) \le 10^9~.
• ~c_i \le 10^3~.

Output

Gồm một dòng duy nhất là giá trị nhỏ nhất của giá trị lớn nhất của bảng số sau khi loại bỏ đi đúng một thao tác.

Ví dụ

Input

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

Output

3

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

Có ~q~ truy vấn, mỗi truy vấn có dạng ~[l,r,x]~, yêu cầu hãy đếm xem có bao nhiêu ~a_i~ với ~i \in [l,r]~ thỏa mãn ~a_i~ là ước hoặc bội của ~x~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên dương ~l,r,x~

Constraints

• ~1 \le n,q \le 2\times10^5~
• ~1 \le a_i \le 2\times10^5~

Output

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

Sample Input 1:

8 5
12 10 3 18 6 72 28 42
1 8 6
3 7 7
2 6 9
1 5 5
4 8 4

Sample Output 1:

6 1 3 1 2