Gọi ~A~ là dãy số với ~A(i)~ được tạo bởi ghép ~i~ số nguyên tố đầu tiên với nhau: ~2, 23, 235, 2357, 235711, 23571113, ... ~.

Cho ~n~ và ~k~, hãy tìm cách xóa ~k~ chữ số ra khỏi số ~A(n)~ để thu được số lớn nhất có thể.

Input

• Gồm một dòng chứa hai số nguyên không âm ~n~ và ~k~ ~(1 \le n \le 50000)~, dữ liệu đảm bảo ~k~ bé hơn số chữ số của ~A(n)~.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 50~.
• ~50\%~ số test không ràng buộc gì thêm.

Sample Input 1:

7 4

Sample Output 1:

711317

Cho mảng ~A~ gồm ~n~ phần tử ~a_1, a_2, \ldots, a_n~. Với mỗi phần tử ~i~ từ ~1~ đến ~n~, hãy tìm ~j~ sao cho ~j < i~ và ~a_j < a_i~ với ~i - j~ nhỏ nhất. Nói cách khác, với mỗi phần tử, hãy tìm phần tử gần nhất về phía bên trái nhỏ hơn nó.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^5~)
• Dòng thứ gồm ~n~ số nguyên dương ~a_1, a_2, \ldots a_n~ (~1 \le a_i \le 10^9)~

Output

• Gồm một dãy ~n~ số, số ở vị trí ~i~ là vị trí phần tử gần nhất về bên trái của ~i~ mà có giá trị bé hơn ~a_i~. Nếu không tồn tại giá trị đó, in ra ~0~.

Sample Input 1

8
2 5 1 4 8 3 2 5

Sample Output 1

0 1 0 3 4 3 3 7

Cho một dãy ~a~ gồm ~n~ phần tử. Ta định nghĩa ~g(l,r) = min (a[i]) \forall (l \le i \le r)~.

Tiếp đó, ta có ~f(k) = max (g(l,r)) \forall (r - l + 1= k)~, hay ~f(k)~ là giá trị lớn nhất của các ~g(l,r)~ với mọi đoạn ~(l,r)~ có độ dài ~k~.

Hãy lập trình tính các ~f(k)~ từ ~1 -> n~.

Input

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

Output

• In ra một dòng gồm ~n~ số miêu tả kết quả của ~f(k)~ từ ~1 -> n~.

Sample Test

Input:

10
1 2 3 4 5 4 3 2 1 6

Output:

6 4 4 3 3 2 2 1 1 1 

Cho một dãy ~a~ gồm ~n~ phần tử phân biệt. Ta định nghĩa hàm ~g(l,r)~ như sau:

• ~g(l,r) = Max(l,r) \oplus MaxSecond(l,r)~. Ở đây, ~\oplus~ là toán tử ~xor~.
• Trong đó ~Max(l,r)~ là số lớn nhất trong đoạn ~[l,r]~, ~MaxSecond(l,r)~ là số lớn thứ hai trong đoạn ~[l,r]~.

Hãy tính ~max(g(l,r))~ với mọi đoạn ~[l,r]~ của dãy ~a~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. ~(1 \le n \le 10^5).~
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^9~ ~\forall (1 \le i \le n))~.

Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 1000~.
• ~50\%~ còn lại không có điều kiện gì thêm.

Sample Input 1:

5
5 2 1 4 3

Sample Output 1:

7

Explanation 1:

• Kết quả chính là ~g(4,5) = 4 \oplus 3 = 7~, hoặc ~g(1,2)~.

Sample Input 2:

5
9 8 3 5 7

Sample Output 2:

15

Explanation 2:

• Kết quả là ~g(2,5)~.

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

Cho lưới ô vuông ~n*n~. Các hàng đánh số từ ~1 ... n~ từ trên xuống dưới, các cột đánh số ~1...n~ từ trái sang phải. Ô ở hàng ~i~, cột ~j~ chứa số nguyên ~a_{ij}~ ~(1 \le a_{ij} \le 200)~.

Hãy đếm số hình chữ nhật của lưới có phần tử nhỏ nhất đúng bằng ~100~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. (~1 \le n \le 1000~).

• ~n~ dòng sau, mỗi dòng gồm ~n~ số nguyên miêu tả lưới ô vuông.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~40\%~ số test có ~n \le 200~.
• ~40\%~ số test có ~n \le 500~.
• ~20\%~ số test có ~n \le 1000~.

Sample Input 1:

3
57 120 87
200 100 150
2 141 135

Sample Output 1:

8

Một dãy các số ~a_1,a_2,...,a_n~ được gọi là dãy kẹp nếu ~a_1 \le a_i \le a_n~, ~\forall i \in [1,n]~. Nếu ~n \le 2~ thì là dãy kẹp nếu ~a_1 \le a_n~.

Các ví dụ về dãy kẹp: ~[1],[1,1],[3,4,3,4],[1,3,2,4]~. Các ví dụ về dãy không phải dãy kẹp: ~[],[2,3,1],[2,1,4,3]~.

Cho mảng ~a = [a_1,a_2,...,a_n]~, hãy đếm xem có bao nhiêu mảng con liên tiếp của ~a~ là dãy kẹp.

Input

• Dòng đầu chứa số nguyên dương ~𝑛~ ~(𝑛 ≤ 10^6)~.
• Dòng sau chứa dãy ~a~ ~(1 \le a_i \le 10^9)~.

Subtask

• Subtask ~1~ ~(10\%)~ : ~n \le 300~
• Subtask ~2~ ~(20\%)~ : ~1 \le n \le 10^5, 1 \le a_i \le 2~
• Subtask ~3~ ~(20\%)~ : ~n \le 5000~
• Subtask ~4~ ~(30\%)~ : ~n \le 10^5~
• Subtask ~5~ ~(20\%)~: Không giới hạn gì thêm

Output

• In ra một số là kết quả bài toán.

Sample Input 1

5
1 2 4 3 5

Sample Output 1

11

Sample Input 1

8
2 1 6 3 6 7 8 5

Sample Output 1

18

Cho một cây vô hướng ~n~ đỉnh với gốc là ~1~, mỗi đỉnh ~u~ có một giá trị là ~c[u]~. Cho ~q~ truy vấn có dạng như sau:

• Truy vấn có dạng "~1~ ~v~". Với truy vấn này, tạm gọi dãy ~u_1, u_2, ..., u_k~ là dãy đỉnh trong đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~v~, (~u_k = v~). Bạn cần tìm một đỉnh ~u_i~ nào đó thỏa mãn ~gcd(c[u_i], c[v]) > 1~ với ~1 \le i < k~. Nếu có nhiều giá trị ~u_i~ thỏa mãn, hãy chọn đỉnh có ~i~ lớn nhất, ngược lại, in ra ~-1~ nếu không có đỉnh nào như vậy.
• Truy vấn có dạng "~2~ ~v~ ~w~". Với truy vấn này, bạn hãy đổi giá trị ~c[v] = w~. Có tối đa ~50~ truy vấn dạng này.

Hãy giải quyết bài toán trên.

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 ~c_1, c_2, ..., c_n~. ~(c_i \le 2*10^6)~
• ~n-1~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u v~ miêu tả cạnh nối giữa hai đỉnh này.
• ~q~ dòng tiếp theo, mỗi dòng miêu tả một truy vấn. Lưu ý rằng, với mọi truy vấn, ~v \le n~, ~w \le 2*10^6~

Output

• In ra kết quả của các truy vấn dạng ~1~ thành từng dòng.

Sample Test

Input

4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4

Output

-1
1
2
-1
1