Cho hai số nguyên dương \(n\) và \(k\). Hãy tìm số nguyên dương thứ \(k\) không chia hết cho \(n\).

Input

• Dòng đầu tiên gồm số nguyên dương \(q\) (\(1 \le q \le 1000\)) - số truy vấn bạn cần trả lời.
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(n\) và \(k\) (\(2 \le n \le 10^9, 1 \le k \le 10^9\)).

Input

• Gồm \(q\) dòng, mỗi dòng là kết quả của truy vấn.

Scoring

Sample

Note:

• Truy vấn 3 7: Các số không chia hết cho \(3\): 1, 2, 4, 5, 7, 8, 10, … → Số thứ 7 là 10.
• Truy vấn 4 12: Các số không chia hết cho \(4\): 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, … → Số thứ 12 là 15.

Một dãy \(a_1, a_2, \dots, a_n\) được gọi là cân bằng nếu có thể chia dãy thành hai đoạn liên tiếp có tổng bằng nhau, tức là tồn tại một vị trí \(p\) (\(1 \leq p < n\)) sao cho tổng giá trị của \(p\) phần tử đầu dùng bằng của \((n - p)\) phần tử cuối:

\(\sum_{i=1}^{p} a_i = \sum_{i=p+1}^{n} a_i\)

Cho một dãy \(a_1, a_2, \dots, a_n\) độ dài \(n\). Bạn có thể biến dổi dãy \(a_1, a_2, \dots, a_n\) bằng cách thực hiện thao tác sau số lần tùy ý. Mỗi lần thực hiện thao tác có thể tùy ý lựa chọn một trong hai hành
động:

• Chọn một vị trí \(i\) (\(1 \leq i \leq n\)) và tăng \(a_i\) lên 1.
• Chọn một vị trí \(i\) (\(1 \leq i \leq n\)) mà \(a_i > 1\) và giảm \(a_i\) cho 1.

Hãy thực hiện thao tác trên ít lần nhất để làm cho dãy a cân bằng.

Input

Dòng đầu tiên chứa số nguyên \(n\) (\(2 \leq n \leq 2 \times 10^5\)) là độ dài dãy \(a\).

Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 20242024\)).

Output

Một số nguyên duy nhất là số lần ít nhất cần thực hiện thao tác.

Scoring

Sample

Notes

Ở ví dụ 1, ta thực hiện cộng \(a_2\) cho 1, trừ \(a_4\) và \(a_5\) cho 1. Sau 3 lần thực hiện thao tác, dãy \(a\) trở thành \(1, 3, 3, 3, 4\), và có vị trí \(p = 3\) thỏa mãn yêu cầu đề bài.

Có \(n + 1\) ngọn núi, ngọn núi thứ \(i\) (\(1 \le i \le n\)) có độ cao \(h_i\). Có \(n\) con mèo đang sống, chú mèo \(i\) nằm ở ngọn núi \(i\), ngọn núi thứ \(n + 1\) có độ cao lớn nhất trong mọi hang (không có con mèo nào sống ở đó). Mỗi ngày những con mèo đều phải tập thể dục theo một quy luật cho trước, con mèo \(i\) sẽ thức hiện \(J_i\) lần nhảy, mỗi lần nhảy con mèo sẽ nhảy qua ngọn núi gần nhất cao hơn và có chỉ số lớn hơn chỉ số ngọn núi hiện tại nó đang đứng. Khi con mèo đã nhảy đến ngọn núi \(n + 1\) thì không thực hiện nhảy tiếp nữa.

Yêu cầu: Hãy xác định độ cao của ngọn núi mà mỗi con mèo sẽ đến sau khi tập thể dục xong (một ngon núi có thể chứa nhiều con mèo). Nếu vị trí mới của con mèo là ngọn núi \(n + 1\) thì ghi \(-1\).

Input:

• Dòng thứ nhất chứa số nguyên dương \(n\) (\(1 \le n \le 10 ^ 6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(h_1\), \(h_2\), …, \(h_n\) (\(1 \le h_i \le 10 ^ 6\)).
• Dòng thứ ba chứa \(n\) số nguyên dương \(J_1, J_2, … J_n\) (\(1 \le J_i\) < \(10^6\)).

Output:

• Một dòng chứa \(n\) số nguyên là độ cao nơi ở mới của mỗi chú mèo.

Scoring

Sample Input:

5 
3 6 7 6 4 
2 1 1 3 2 

Sample Output:

7 7 -1 -1 -1

Giải thích:

• Mèo đầu tiên nhảy \(2\) lần từ ngọn núi \(1 \rightarrow 2 \rightarrow 3\).
• Mèo thứ hai nhảy \(1\) lần từ \(2 \rightarrow 3\).
• Mèo thứ ba nhảy \(1\) lần từ \(3 \rightarrow 6 (n + 1)\) nên in ra \(-1\).
• Mèo thứ tư nhảy \(1\) lần từ \(4 \rightarrow 6 (n + 1)\) nên in ra \(-1\).
• Mèo thứ năm nhảy \(1\) lần từ \(5 \rightarrow 6 (n + 1)\) nên in ra \(-1\).

Vào một ngày nọ, bạn của Long giới thiệu cho cậu một tựa game chiến thuật khá nổi tiếng dạo gần đây. Trò chơi cung cấp cho Long \(n\) quân lính, quân lính thứ \(i\) (\(1 \leq i \leq n\)) có chỉ số sức mạnh là \(p_i\). Ở mỗi màn chơi sẽ có một con quái vật, giả sử con quái vật có chỉ số sức mạnh là \(k\), để tiêu diệt được nó Long phải chọn ra một đội hình gồm các quân lính sao cho tổng sức mạnh các quân lính đó không nhỏ hơn \(k\).

Biết rằng trò chơi có nhiều màn và các quân lính cậu đã chọn vào đội hình sẽ biến mất và không thể sử dụng lại, Long phải tính toán làm sao để sử dụng tối ưu các quân lính của mình. Cậu nhận thấy rằng trong đội hình có thể có một vài quân lính không quan trọng.

Vì vậy nên Long muốn xác định xem trong \(n\) quân lính, quân lính thứ \(i\) có quan trọng hay không. Quân lính thứ \(i\) (\(1 \leq i \leq n\)) được xem là quan trọng hay không dựa theo quy tắc sau:

• Nếu như với bất kỳ đội hình tiêu diệt được quái vật có chứa quân lính thứ \(i\), đội hình mới được tạo ra bằng cách bỏ quân lính đó đi và giữ nguyên những quân lính còn lại vẫn có thể tiêu diệt được quái vật, thì quân lính thứ \(i\) được xem là không quan trọng.
• Ngược lại, quân lính thứ \(i\) được xem là quan trọng.

Lưu ý: Đội hình có thể không có quân lính nào cả.

Vì số lượng quân lính là rất lớn nên Long nhờ bạn xác định giúp cậu.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq n, k \leq 5000\)) lần lượt là số lượng quân lính và chỉ số sức mạnh của quái vật.
• Dòng tiếp theo chứa \(n\) số nguyên \(p_i\) (\(1 \leq p_i \leq 10^9\)) là chỉ số sức mạnh của các quân lính.

Output

• In ra một dãy nhị phân độ dài \(n\), bit thứ \(i\) bằng \(0\) nếu quân lính thứ \(i\) không quan trọng, bằng \(1\) nếu ngược lại.

## Scoring

Sample

Note

• Đội hình tiêu diệt được quái vật chứa quân lính thứ nhất là \(\{4, 6\}\), \(\{4, 1, 6\}\), \(\{4, 6, 2\}\), \(\{4, 1, 6, 2\}\). Vì trong đội hình \(\{4, 6\}\), khi bỏ quân lính thứ nhất đi thì đội hình không thể tiêu diệt được quái vật nên quân lính thứ nhất được xem là quan trọng.
• Đội hình tiêu diệt được quái vật chứa quân lính thứ hai là \(\{4, 1, 6\}\), \(\{4, 1, 6, 2\}\). Vì trong mọi đội hình, khi bỏ quân lính thứ hai đi thì đội hình vẫn tiêu diệt được quái vật nên quân lính thứ hai được xem là không quan trọng.

Chow đang đi nghỉ! Với một số tiến bộ công nghệ gần đây, Chow sẽ đi bằng các chuyến bay có công nghệ cao, thậm chí có thể du hành thời gian. Hơn nữa, sẽ không có vấn đề gì nếu hai phiên bản "song song" của Chow gặp nhau.

Trong nước có \(N\) sân bay được đánh số \(1,2,...,N\) và \(M\) chuyến bay du hành thời gian \((1 \leq N,M \leq 200000)\). Chuyến bay \(j\) rời sân bay \(c_j\) tại thời điểm \(r_j\), và đến sân bay \(d_j\) tại thời điểm \(s_j\) \((0 \leq r_j,s_j \leq 10^9)\). Ngoài ra, nó phải mất \(a_i\) thời gian cho việc quá cảnh tại sân bay \(i (1 \leq a_i \leq 10^9)\). (Ng hĩa là, nếu Chow đáp chuyến bay đến sân bay \(i\) tại thời điểm \(s\), thì nó có thể chuyển sang chuyến bay rời sân bay vào thời điểm \(r\) nếu \(s+a_i \leq r\). Việc quá cảnh không diễn ra khi Chow đến sân bay.)

Chow bắt đầu tại thành phố \(1\) vào lúc \(0\) . Đối với mỗi sân bay từ \(1\) đến \(N\), thời gian sớm nhất mà Chow có thể đến đó là khi nào?

Input

• Dòng đầu tiên chứa N và M.
• \(M\) dòng tiếp theo mô tả các chuyến bay. Dòng thứ \(j\) trong số các dòng này chứa \(c_j\) , \(r_j\) , \(d_j\) , \(s_j\) theo thứ tự đó. \((1 \leq c_j,d_j \leq N, 0 \leq r_j,s_j \leq 10^9 )\)
• Dòng tiếp theo mô tả các sân bay. Nó chứa \(N\) số nguyên cách nhau bằng dấu cách \(a_1,…,a_N\).

Output

In ra \(N\) dòng, dòng thứ \(i\) chứa thời gian sớm nhất Chow có thể đến sân bay \(i\), hoặc \(-1\) nếu Chow không thể đến sân bay đó.

Scoring

Sample

Note

Sample 1

• Chow có thể đi \(3\) chuyến theo thứ tự liệt kê, điều này cho phép nó đến sân bay \(1\) và \(2\) vào thời điểm \(0\), và sân bay \(3\) vào thời điểm \(20\).
• Lưu ý rằng tuyến đường này đi qua sân bay \(2\) hai lần, lần đầu tiên từ thời điểm \(10-11\) và sau đó từ thời điểm \(0-1\).

Sample 2

Trong trường hợp này, Chow có thể bắt chuyến bay \(1\), đến sân bay \(2\) lúc thời điểm 10. Tuy nhiên, cô ấy không đến kịp để bắt chuyến bay \(2\), vì thời gian khởi hành là thời điểm \(10\) và cô ấy không thể quá cảnh trong 1 đơn vị thời gian.