Ngoài giỏi thuật toán, Đăng còn là một chuyên gia về bảo mật! Đăng biết rằng một đoạn code bất kì có thể biểu diễn dưới dạng một dãy nhị phân. Cho một số đoạn code có chứa nội dung nguy hiểm (ví dụ như virus), ta có thể tìm những đoạn code tương tự bằng cách sử dụng thuật toán giống như các thuật toán so khớp chuỗi. Với ý tưởng đó, Đăng đố các bạn bài toán sau:

Cho một cơ sở dữ liệu gồm ~N~ đoạn code, biểu diễn dưới dạng các dãy nhị phân có độ dài ~M~ bit. Bạn cần xử lý truy vấn, mỗi truy vấn thuộc 1 trong 2 dạng sau:

• 1 u id: đảo ngược bit ở vị trí thứ ~id~ của dãy nhị phân thứ ~u~ ~(1 \le u \le N, 1 \le id \le M)~
• 2 x y: cho biết số vị trí ~j~ mà bit thứ ~j~ của dãy nhị phân thứ ~x~ và bit thứ ~j~ của dãy nhị phân thứ ~y~ là khác nhau ~(1 \le x, y \le N)~

Input

• Dòng đầu tiên của input chứa hai số nguyên ~N~ và ~M~ ~(1 \le N, M, \le 10^5)~, lần lượt là số dãy nhị phân và độ dài của từng dãy.
• ~N~ dòng tiếp theo, mỗi dòng chứa một chuỗi nhị phân gồm ~M~ bit.
• Dòng tiếp theo chứa ~Q~ ~(1 \le Q \le 2 \times 10^5)~, là số truy vấn bạn cần xử lý.
• ~Q~ dòng tiếp theo, mỗi dòng là một truy vấn với cấu trúc trên.

Tổng số lượng bit của các chuỗi nhị phân không vượt quá ~10^5~

Output

Với mỗi truy vấn loại 2, bạn cần đưa ra câu trả lời trên một dòng.

Sample Input

3 3
110
011
000
3
2 1 2
1 3 1
2 1 3

Sample Output

2
1

Subtasks

• ~30\%~ số điểm của bài tương ứng với các test có ~1 \le N, M \le 300~, ~1 \le Q \le 2000~.

Thành phố vừa hết giãn cách do dịch bệnh đã qua đi nên các tuyến đường đông đúc trở lại. Các hàng quán, khu chợ, siêu thị cũng trở nên tấp nập và nhộn nhịp như những năm trước đây. Tuy nhiên, để tránh tình trạng kẹt xe và ùn tắc ở các tuyến đường, các thông số thống kê được các nhà chức trách thu thập để điều phối lưu lượng giao thông hợp lý hơn.

Cụ thể, thành phố được mô tả dưới dạng một đồ thị gồm ~n~ đỉnh và ~m~ cạnh tương ứng với ~n~ địa điểm và ~m~ tuyến đường hai chiều ~(u,v)~. Trên mỗi cạnh có một trọng số ứng với lưu lượng giao thông tại tuyến đường đó. Biết rằng, không có tuyến đường nào mà hai đầu của tuyến đường đó là cùng một địa điểm, và không có hai địa điểm nào được liên kết bởi nhiều hơn một tuyến đường. Đồng thời, tại một địa điểm bất kỳ có thể di chuyển được đến tất cả các địa điểm khác thông qua một hoặc nhiều tuyến đường.

Các nhà chức trách muốn biết rằng liệu với mỗi tuyến đường ~(u,v)~, có thể chọn thêm ~n-2~ tuyến đường khác sao cho ~n~ địa điểm vẫn được liên kết với nhau và có tổng lưu lượng là nhỏ nhất.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~ – là số lượng địa điểm và số lượng tuyến đường trong thành phố.

~m~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n, u_i ≠ v_i, 1 \le w_i \le 10^9)~ – biểu diễn hai địa điểm đầu mút của tuyến đường thứ i và lưu lượng của tuyến đường đó.

Output

Gồm ~m~ dòng, dòng thứ ~i~ chứa tổng lưu lượng nhỏ nhất của ~n-1~ tuyến đường liên kết ~n~ địa điểm và có chứa tuyến đường thứ ~i~.

Lưu ý: Các địa điểm và tuyến đường được đánh số thứ tự từ ~1~.

Sample Input

5 10
1 2 1
1 3 3
1 4 1
1 5 4
2 3 2
2 4 4
2 5 7
3 4 7
3 5 7
4 5 10

Sample Output

8
9
8
8
8
11
11
13
11
14

Subtasks:

• ~40\%~ số lượng test có ~1 \le n \le 50, n-1 \le m \le n×(n-1)/2, w_i \le 100~
• ~40\%~ số lượng test có ~1 \le n \le 10^4, n-1 \le m \le min(n×(n-1)/2, 2×10^5), w_i \le 10^5~
• ~20\%~ số lượng test có ~1 \le n, m \le 2×10^5, w_i \le 10^9~

Các nhà thám hiểm vừa đưa một con Robot MS227 vào một hang động bí ẩn để thu thập dữ liệu. Bề mặt hang động được mô phỏng dưới dạng một lưới ô vuông có kích thước ~n×n~. Robot bắt đầu di chuyển từ cửa hang động tại ô ~(1,1)~ và kết thúc hành trình thu thập dữ liệu tại lối thoát của hang động ở vị trí ~(n,n)~. Ở mỗi bước, Robot khi đứng tại ô ~(i,j)~ chỉ có thể di chuyển đến ô phía trên ~(i,j+1)~ hoặc ô bên phải ~(i+1,j)~.

Các nhà thám hiểm cho biết rằng bên trong hang động có một sinh vật lạ chưa từng được biết đến đang ẩn náu. Sinh vật này có số lượng cá thể đang ẩn mình trong hang động là ~k^2~, và các cá thể đó đang nằm tại các vị trí ~(a+i,b+j)~ bên trong hang động (với ~i~ và ~j~ là hai số nguyên thỏa ~0 \le i < k, 0 \le j < k~).

Mỗi cá thể của sinh vật này có một độ kiên nhẫn nhất định ban đầu là ~s~. Mỗi lần Robot MS227 di chuyển đến vị trí ~(x,y)~, độ kiên nhẫn của cá thể tại vị trí ~(u,v)~ sẽ bị giảm đi một lượng là (~|u-x|+|v-y|~). Biết rằng, khi một cá thể hết kiên nhẫn (độ kiên nhẫn < 0), cá thể đó sẽ hoảng loạn và làm cho thông tin thu thập được từ robot bị nhầm lẫn. Do đó, các nhà thám hiểm mong muốn tìm một cách di chuyển cho Robot từ cửa hang đến lối thoát mà không làm cho bất kỳ cá thể nào hoảng loạn. Biết rằng, vì Robot MS227 có kích thước rất nhỏ nên nó vẫn có thể di chuyển qua vị trí mà các cá thể đang nằm.

Input

Gồm một dòng duy nhất chứa ~5~ số nguyên ~n, s, a, b, k~ thỏa:

• ~2 \le n \le 10^5~
• ~0 \le s \le 10^{14}~
• ~1 \le a \le n-k+1~
• ~1 \le b \le n-k+1~
• ~1 \le k \le n~

Output

Trong trường hợp có kết quả, in ra màn hình một dòng duy nhất một chuỗi chứa ~2n-2~ ký tự để biểu diễn cách di chuyển của Robot. Cụ thể, ký tự tại vị trí thứ ~i~ là ~E~ cho biết Robot di chuyển sang phải, hoặc là ~N~ nếu Robot di chuyển hướng lên trên tại bước thứ ~i~.

Nếu có nhiều cách di chuyển khác nhau thỏa mãn, in ra cách di chuyển có thứ tự từ điển nhỏ nhất. Ký tự ~E~ đứng trước ký tự ~N~ trong thứ tự từ điển.

Nếu không có đường đi nào thỏa mãn, in ra Impossible.

Sample Input 1

2 4 1 1 2

Sample Output 1

EN

Sample Input 2

5 22 4 3 2

Sample Output 2

EEENENNN

Sample Input 3

4 13 2 1 1

Sample Output 3

Impossible

Subtask

• ~30\%~ số điểm của bài tương ứng với các test có ~2 \le n \le 100~.
• ~20\%~ số điểm khác của bài tương ứng với các test có ~n \le 1000~.
• ~50\%~ số điểm còn lại của bài tương ứng với cá test có ~n \le 10^5~.

Nhật đang chơi xếp bi trước sân nhà vào một buổi chiều mùa thu se lạnh. Nhật có ~N~ viên bi khác nhau và Nhật đã rải chúng tại những vị trí khác nhau trên sân. Nhật vừa được học về bài tam giác vuông ở lớp toán vào buổi sáng, do đó Nhật muốn biết rằng có bao nhiêu bộ ba viên bi trên sân tạo thành một tam giác vuông.

Input

• Dòng đầu chứa ~N~ ~(3 \le N \le 1500)~ là số viên bi mà Nhật có.
• ~N~ dòng tiếp theo, mỗi dòng chứa ~x_i, y_i~ ~(-10^9 \le x_i,y_i \le 10^9)~ là toạ độ của các viên bi.
• Biết rằng không có hai viên bi nào nằm cùng một vị trí trên sân.

Output

Một số nguyên là số bộ tam giác vuông mà các viên bi của Nhật tạo thành.

Sample Input 1

3
4 2
2 1
1 3

Sample Output 1

1

Sample Input 2

4
5 0
2 6
8 6
5 7

Sample Output 2

0

Sample Input 3

5
-1 1
-1 0
0 0
1 0
1 1

Sample Output 3

7

Subtasks

• ~30\%~ số điểm của bài tương ứng với các test có ~3 \le N \le 300~.

Cây chỉ số nhị phân (Binary Indexed Tree), hay còn gọi là Fenwick Tree, là một cấu trúc dữ liệu dùng để lưu tổng cộng dồn của một mảng một cách hiệu quả. Cấu trúc này cho phép cập nhật một phần tử và truy vấn tổng cộng dồn tới một vị trí trong ~O(log \space n)~.

Cho dãy số nguyên ~A~ đánh số từ 1, ta gọi dãy ~B~ là cây chỉ số nhị phân được xây dựng dựa trên ~A~ như sau:

• Với mỗi chỉ số ~i~, ta xét biểu diễn nhị phân của ~i~, đánh số các bit theo thứ tự từ nhỏ đến lớn bắt đầu từ 0.
• Gọi vị trí bit 1 nhỏ nhất của ~i~ là ~k~.
• Khi đó ~B[i]~ là tổng của ~2^k~ phần tử liên tiếp của ~A~, kết thúc tại ~i~.
• Ví dụ: ta có ~6 = 2^2 + 2^1~, suy ra ~k=1~, do đó ~B[6] = A[5] + A[6]~.

Sau đây là hình ảnh minh họa cây chỉ số nhị phân cho dãy gồm 8 phần tử, lấy từ VNOI Wiki, với "bit" chính là dãy ~B~:

Đăng xây dựng một hệ thống cơ sở dữ liệu hỗ trợ tính toán nhanh, trong đó có dùng một cây chỉ số nhị phân. Tuy nhiên, do một sự cố mất điện, ổ cứng của máy đã bị hư hỏng, và Đăng đã mất toàn bộ dãy ~A~, chỉ còn lại dãy ~B~. Ngay cả dãy ~B~ cũng bị mất một số phần tử. Với những phần tử trong dãy lưu ở những vùng ổ cứng bị hư hỏng, khi đọc lên sẽ được thay bằng kí tự "?".

Từ những phần tử của dãy ~B~ còn lại, bạn hãy khôi phục lại nhiều phần tử nhất có thể của dãy ~A~.

Input

Dòng đầu tiên của input chứa số nguyên ~N~ ~(1 ≤ N ≤ 10^5)~, số phần tử của dãy ~B~.

Dòng thứ hai chứa ~N~ số nguyên không âm là các phần tử của dãy ~B~, cách nhau bởi khoảng trắng.

Output

In ra dãy ~A~ đã được khôi phục trên một dòng, với dấu "?" cho những vị trí không thể khôi phục được, các phần tử cách nhau bởi một khoảng trắng.

Các phần tử của dãy ~A~ là các số nguyên không âm có giá trị không vượt quá ~10^4~.

Sample Input

2
? 2

Sample Output

? ?

Subtask

• ~30\%~ số điểm của bài tương ứng với các test không có dấu "?" trong input.

Note

Trong test đề bài, ta chỉ biết được tổng của 2 phần tử, thông tin này là không đủ để ta suy ra từng phần tử là gì.