Ôn tập

Trên trục \(\text{Ox}\), bạn đang đứng ở vị trí \(0\).

Ở mỗi bước, bạn có thể tiến lên hoặc lùi xuống \(2\) bước hoặc \(3\) bước.

Ví dụ: Hiện tại bạn đang đứng ở vị trí \(x\), vậy thì ở bước tiếp theo bạn có thể đến \(1\) trong \(4\) vị trí: \((x+2),(x-2),(x+3),(x-3)\).

Yêu cầu:
Mục tiêu của bạn là đến được vị trí \(n\). Tìm số lượng bước ít nhất để thực hiện điều đó.

Input

• Dòng đầu: \(t\) - số test \((1 \le t \le 5\times 10^5)\)
• \(t\) dòng sau: mỗi dòng chứa một số \(n\) \((n \in \mathbb{N}^*, n \le 10^{18})\)

Output

• Ứng với mỗi test, in ra đáp án cần tìm.

Example

4
1
3
4
12

2
1
2
4

Cho dãy \(A\) có \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) và số nguyên \(k\) (\(1 \le k \le n \le 10^6\)).

Yêu cầu: Tìm độ dài đoạn con ngắn nhất chứa đủ \(k\) phần tử mà số lượng ước của mỗi phần tử này là nhiều nhất trong dãy.

Input

• Dòng một gồm hai số nguyên dương \(n, k\).
• Dòng hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^7, \forall i=\overline{1, n}\)).
• Các số nguyên trong tệp dữ liệu được ghi cách nhau ít nhất một dấu cách trống.

Output

• Ghi ra một số nguyên thỏa mãn yêu cầu, trường hợp không có đoạn con nào đủ \(k\) phần tử thỏa mãn yêu cầu thì ghi \(-1\).

Example

8 3
6 2 3 8 4 10 9 10

5

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3, k \le 10^3, a_i \le 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^5, k \le 10^4, a_i \le 10^6\).
• Subtask \(3\) (\(10\%\) số điểm): \(n \le 10^6, k \le 10^6, a_i \le 10^6\).
• Subtask \(4\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.

Thuận là chủ của thương hiệu Mountain Game - chuyên cung cấp dịch vụ leo núi dưới dạng một trò chơi thi đấu. Khu vực tổ chức thi leo núi của Mountain Game có thể được chia thành \(n\) cấp bậc với độ cao tăng dần. Trong đó, \(a_i\) là độ khó khăn để vượt từ cấp \(i-1\) lên cấp \(i\). Ta quy ước cấp \(0\) là mặt đất, nơi mỗi người chơi sẽ bắt đầu.
Theo luật chơi, nếu người chơi hiện đang có mức độ thể lực là \(x\), thì người đó chỉ vượt qua được những cấp bậc có độ khó không lớn hơn \(x\). Việc di chuyển lên các cấp không tiêu hao thể lực.
Sau khi đi tới cấp độ \(i\), bất kì người chơi nào cũng sẽ nhận được một buff hoặc nerf tương ứng, giúp thể lực của người đó giảm đi một lượng \(b_i\), tức là

(nếu \(b_i\) âm, tức thể lực của người chơi được tăng lên - buff). Ta giả sử có vô hạn buff / nerf tại mỗi cấp, nhưng mỗi người chơi khi tiến tới cấp \(i\) sẽ được nhận buff tại tầng đó một lần duy nhất.
Luật chơi cũng giới hạn người chơi di chuyển từ cấp thấp lên cấp cao hơn, lần lượt, tức từ cấp \(i\) lên cấp \(i+1\) theo thứ tự \(1,2,3,\dots,n\).
Ngoài ra, để đảm bảo an toàn, khi một người chơi không thể tiến thêm được nữa (không đủ thể lực hoặc đã ở cấp cuối cùng), trên mỗi cấp đã có bố trí sẵn phòng nghỉ ngơi và cánh cửa thần kì để mỗi người chơi dừng lại và trở về mà không tiêu hao thể lực.
Dĩ nhiên, khi vượt qua một màn với độ khó khăn là \(x\) thì người chơi cũng được thưởng thêm một lượng tiền là \(x\) USD. Phần thưởng này đã thu hút rất nhiều người chơi đăng ký.
Có \(q\) người chơi đã đăng ký Mountain Game, với mỗi người thứ \(j\), Thuận biết được thể lực của người đó là \(k_j\) (theo thông tin đăng ký). Để dự trù kinh phí, Thuận cần tính trước với mỗi người, tổng tiền thưởng cần chuẩn bị cho anh ta là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n,q \leq 5 \times 10^{5})\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n (1 \le a_i \le 10^9)\) là độ khó của các cấp độ.
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n (|b_i| \le 10^9)\) là mức độ thay đổi thể lực của từng cấp.
• \(q\) dòng tiếp theo, dòng thứ \(j\) chứa một số \(k_j\) \((1 \leq k_j \leq 10^{15})\) là thể lực của người chơi thứ \(j\).

Output

• Với mỗi người chơi, in ra lượng tiền tối đa của người đó có thể được thưởng, trên một dòng riêng biệt.

Scoring

• Subtask \(1\) (\(24\%\) số điểm): \(n,q \le 5000\).
• Subtask \(2\) (\(24\%\) số điểm): \(b_i = 0\).
• Subtask \(3\) (\(26\%\) số điểm): \(b_i < 0\).
• Subtask \(4\) (\(26\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
2 3 5
2 -1 1
1
2
5
8

0
2
5
10

Trong một trò chơi có \(n\) đứa trẻ (đánh số \(1,2,…,n\)) trong một vòng tròn. Trong trò chơi, cứ mỗi hai đứa trẻ thì đứa trẻ sau sẽ bị loại khỏi vòng tròn, cho đến khi không còn đứa trẻ nào.
Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: "Khi có \(n\) đứa trẻ thì đứa trẻ thứ \(k\) sẽ bị loại bỏ là ai?"

Input

• Dòng đầu tiên là \(q\): số lượng truy vấn
• \(q\) dòng tiếp theo, mỗi dòng chứa 2 số \(n\) và \(k\): số đứa trẻ và thứ tự bị loại bỏ của đứa trẻ

Constraints

• \(1 \leq q \leq 10^5\)
• \(1 \leq k \leq n \leq 10^9\)

Output

• \(q\) dòng: đáp án của mỗi truy vấn

Example

4
7 1
7 3
2 2
1337 1313

2
6
1
1107