Shin cậu bé bút chì đang chuẩn bị sách vở cho năm học mới. Mẹ Misae đã mua cho cậu dụng cụ học tập gồm: ~A~ chiếc bút chì và ~B~ cái gọt bút.

Một cái bút chì có thể gọt tối đa ~X~ lần. Một cái gọt bút chì có thể sử dụng tối đa ~Y~ lần. Những chiếc bút khi mua về có thể sử dụng luôn mà không cần gọt.

Shin cần mua thêm ~C~ bút chì và ~D~ gọt bút sao cho có thể sử dụng hết, không còn thừa cái bút chì hoặc gọt nào cả.

Tìm giá trị ~C + D~ nhỏ nhất. Nếu không tồn tại đáp án, in ra ~-1~

Input

Dòng đầu tiên chứa số nguyên ~T~ là số bộ test ~(1 \le T \le 100)~

Mỗi bộ test trên một dòng chứa bốn số nguyên ~A, B, X, Y~ ~(0 \le A, B \le 100, 1 \le X, Y \le 100)~.

Output

In ra đáp án cho từng bộ test:

• In ra giá trị ~C + D~ nhỏ nhất để sử dụng hết tất cả bút chì và gọt bút mà không còn thừa.

• Nếu không tồn tại cách sử dụng hết, in ra ~-1~.

Sample Input 1

2
1 2 3 4 
1 1 1 1

Sample Output 1

4
0

Notes

Trong ví dụ 1, Shin sẽ mua thêm 3 bút chì và 1 chiếc gọt.

Trong ví dụ 2, Shin không cần mua gì cả.

Cho một số nguyên dương ~n~. Tìm số nguyên ~x~ nhỏ nhất sao cho ~x \ge n~ và tổng số lần xuất hiện các chữ số ~0~ đến ~9~ trong số ~x~ và trong số ~x^2~ tối đa 2 lần. Nếu không tồn tại số ~x~, in ra ~-1~.

Input

Nhập vào ~t~ ~(1 \le t \le 10^5)~ truy vấn,

Mỗi truy vấn là một số nguyên dương ~n~ ~(1 \le n \le 4 \times 10^6)~.

Output

Với mỗi truy vấn, in ra số nguyên ~x~ nhỏ nhất thoả mãn đề bài. Nếu không tồn tại số ~x~, in ra ~-1~.

Scoring

Sample Input 1

10
1
2
3
4
5
6
7
8
9
10

Sample Output 1

1
2
3
4
5
6
7
8
9
12

Sample Input 2

2
1000000
3000000

Sample Output 2

1032857
3081672

Notes

Nếu ~n = 10~, ta thấy giá trị ~x = 12~ là đáp án. Vì ~x = 12~ và ~x^2 = 144~ không chứa chữ số nào xuất hiện quá ~2~ lần. Nếu ~x = 11~ và ~x^2 = 121~ thì chữ số ~1~ xuất hiện ~4~ lần, do đó không thoả mãn.

Nếu ~n = 1000000~, ta thấy giá trị ~x = 1032857~ là đáp án. Vì ~x = 1032857~ và ~x^2 = 1066793582449~ không chứa chữ số nào xuất hiện quá ~2~ lần.

Cho ~n~ sợi dây, sợi dây thứ ~i~ có độ dài ~A_i~ đơn vị độ dài. Giả sử có một sợi dây độ dài ~X~, nếu ta cắt một đoạn độ dài ~0 < t < X~ thì ta sẽ được hai sợi dây mới độ dài ~t~ và ~X - t~.

Được thực hiện ~k~ phép cắt dây, hãy tìm độ dài nhỏ nhất có thể của sợi dây dài nhất nhé.

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le n \le 2 \times 10^5, 0 \le k \le 10^9)~, thể hiện số lượng sợi dây và số lượng phép cắt thực hiện.

Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le 10^9)~ - độ dài ban đầu của ~n~ sợi dây.

Output

Gọi ~S~ là độ dài nhỏ nhất của sợi dây dài nhất, có thể cắt được sau ~k~ phép cắt dây. In ra giá trị ~S~ làm tròn lên đến phần nguyên.

Scoring

Sample Input 1

5 1
3 3 3 4 5

Sample Output 1

4

Sample Input 2

2 3
7 9

Sample Output 2

4

Notes

Trong test ví dụ thứ hai, ta có thể thực hiện lần lượt các phép cắt như sau:

• Với sợi dây độ dài ~7~, ta có thể cắt ra thành hai sợi dây độ dài ~\frac{7}{2}~.

• Với sợi dây độ dài ~9~, ta có thể cắt ra thành hai sợi dây độ dài ~3~ và ~6~.

• Với sợi dây độ dài ~6~, ta có thể cắt ra thành hai sợi dây độ dài ~3~.

Vậy sợi dây có độ dài lớn nhất là ~\frac{7}{2}~, ta cần in ra giá trị làm tròn lên là ~4~. Ta có thể chứng minh đây là phương án tối ưu.

Cho một đoạn đường được biểu diễn bởi các điểm đánh số từ ~0~ đến ~10^9~, với điểm ~0~ là biên trái của đường. Đoạn đường được chia làm hai làn, gọi lần lượt là chiều dương và chiều âm. Trên làn đường chiều dương, bạn chỉ có thể đi xe từ một điểm tới một điểm khác có vị trí lớn hơn vị trí của điểm xuất phát. Ở chiều âm, bạn chỉ có thể đi xe từ một điểm tới một điểm khác có vị trí bé hơn vị trí của điểm xuất phát.

Hai làn đường được ngăn cách bởi các dải phân cách cứng. Ngoài ra, sẽ có ~n~ đoạn đường không giao nhau ~[L, R]~ mà ở đó không có dải phân cách và bạn có thể di chuyển qua lại giữa hai làn đường thông qua các đoạn đường đó.

Bạn có ~q~ kế hoạch, với kế hoạch thứ ~i~, bạn cần di chuyển từ vị trí có tọa độ ~x~ trên làn đường theo chiều âm tới vị trí có tọa độ ~y~ trên làn đường theo chiều dương. Theo luật giao thông, bạn không thể di chuyển bằng xe máy theo chiều dương khi đang ở làn đường theo chiều âm và ngược lại. Tuy nhiên, bạn có thể xuống xe và dắt bộ ngược chiều đường. Với mỗi đơn vị độ dài mà bạn dắt xe đi bộ, bạn sẽ tốn ~1~ thể lực.

Hiện tại, bạn đang có ~k~ thể lực và bạn muốn biết mình sẽ phải di chuyển ít nhất bao nhiêu đơn vị độ dài (bao gồm cả đi xe và dắt bộ) để đến được vị trí mình cần.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 2 \cdot 10^5~) — số đoạn đường không có dải phân cách và số kế hoạch.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa hai số nguyên ~L_i~ và ~R_i~ (~0 \le L_i \le R_i \le 10^9~) — hai đầu mút trái và phải của đoạn đường không có dải phân cách thứ ~i~. Đầu vào đảm bảo không có hai đoạn đường nào giao nhau.

Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa ba số nguyên ~x~, ~y~ và ~k~ (~0 \le x, y, k \le 10^9~) mô tả một kế hoạch.

Output

In ra ~q~ dòng, mỗi dòng chứa một số nguyên là đáp án của kế hoạch tương ứng. Trong trường hợp không tồn tại cách di chuyển, in ra -1.

Scoring

Sample Input 1

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

Sample Output 1

1
2
6
-1

Notes

Ở truy vấn đầu tiên, cách đi tối ưu là qua đường tại vị trí ~3~ rồi đi xe tới vị trí ~4~.

Ở truy vấn thứ hai, có hai cách di chuyển:

• Đi xe từ vị trí ~4~ tới vị trí ~3~ trên làn đường âm, qua đường và đi xe từ vị trí ~3~ tới vị trí ~4~ trên làn đường dương, tốn ~0~ thể lực.

• Dắt bộ từ vị trí ~4~ tới vị trí ~5~ trên làn đường âm, qua đường và dắt bộ từ vị trí ~5~ tới vị trí ~4~ trên làn đường dương, tốn ~2~ thể lực.

Ở truy vấn cuối cùng, không có cách nào để di chuyển mà chỉ tốn tối đa ~1~ thể lực.

Cho một dãy hoán vị độ dài ~n~. Lihwy sẽ thực hiện thao tác sau đúng một lần: Chọn ra một dãy con (không cần liên tiếp) ~a_{i_1}, a_{i_2}, \cdots, a_{i_{k - 1}}, a_{i_k}~ (~1 \le i_1 < i_2 < \cdots < i_k \le n~) và đảo ngược dãy con đó thành ~a_{i_k}, a_{i_{k - 1}}, \cdots, a_{i_2}, a_{i_1}~.

Một dãy hoán vị ~a~ độ dài ~n~ là dãy có các số nguyên từ ~1~ đến ~n~ xuất hiện đúng một lần trong dãy. Một nghịch thế là một cặp chỉ số (~i, j~) mà ~i < j~ và ~a_i > a_j~.

Hãy giúp Lihwy tính số nghịch thế nhỏ nhất có thể của dãy sau khi thực hiện thao tác nhé !

Input

Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 5000~) - độ dài của dãy hoán vị.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~). Các số nguyên này đôi một phân biệt.

Output

In ra số nghịch thế nhỏ nhất có thể của dãy sau khi thực hiện thao tác.

Scoring

Sample Input 1

5
5 4 2 3 1

Sample Output 1

1

Sample Input 2

4
1 2 3 4

Sample Output 2

0

Notes

Trong ví dụ thứ nhất, ta có thể chọn dãy con ~[5, 4, 2, 1]~ và đảo ngược nó thành ~[1, 2, 4 , 5]~. Khi đó ta có dãy mới ~[1, 2, 4, 3, 5]~ có số nghịch thế là ~1~.

Trong ví dụ thứ hai, ta có thể chọn dãy con ~[2]~. Khi đó dãy không đổi và có số nghịch thế là ~0~.

Cho dãy nhị phân độ dài ~n~ và ~q~ truy vấn:

• ~i~: Gán ~a_i = 1 - a_i~.

Sau mỗi truy vấn, bạn cần tìm ~k~ lớn nhất sao cho tồn tại dãy số nguyên ~1 \leq i_1 < i_2 < \ldots < i_k \leq n~ thoả mãn ~a_{i_{j - 1}} + a_{i_{j + 1}} = 1~ với mọi ~1 < j < k~. In ra ~k~ tìm được.

Input

Dòng đầu gồm số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~.

Dòng thứ hai gồm ~n~ ký tự ~0~ hoặc ~1~ thể hiện dãy nhị phân.

Dòng thứ ba chứa số nguyên dương ~q~ ~(1 \leq q \leq 10^5)~.

~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~i~ ~(1 \leq i \leq n~) thể hiện một truy vấn.

Output

In ra ~q~ dòng, mỗi dòng gồm một số nguyên dương là độ dài dãy con lớn nhất tìm được sau truy vấn tương ứng.

Scoring

Sample Input 1

7
1111111
4
1
2
5
7

Sample Output 1

3
4
5
6

Sample Input 2

1
1
2
1
1

Sample Output 2

1
1

Note:

Ở test ví dụ đầu tiên:

Sau truy vấn đầu tiên, dãy trở thành 0111111. Dãy con so le dài nhất tìm được là 011, có độ dài là ~3~.

Sau truy vấn thứ hai, dãy trở thành 0011111. Dãy con so le dài nhất tìm được là 0011, có độ dài là ~4~.

Sau truy vấn thứ ba, dãy trở thành 0011011. Dãy con so le dài nhất tìm được là 00110, có độ dài là ~5~.

Sau truy vấn thứ tư, dãy trở thành 0011010. Dãy con so le dài nhất tìm được là 001100, có độ dài là ~6~.