Các sinh vật phải vượt qua một bài vô cùng hóc búa từ Ngọc Hoàng, bài toán được phát biểu như sau:

Cho một dãy số ~n~ số nguyên dương ~a_1, a_2,\ldots, a_n~. Với mỗi số nguyên dương ~a_i~, thí sinh cần đếm xem có bao nhiêu nghiệm nguyên của phương trình ~x + y + gcd(x, y) = a_i~.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \leq n \leq 2 \cdot 10^5~).

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ (~1 \leq a_i \leq 4 \cdot 10^6~).

Output

Một dòng duy nhất chứa ~n~ số nguyên dương là đáp án của bạn.

Scoring

Sample Input 1

3
6 10 13

Sample Output 1

5 8 4

Sample Input 2

6
327 869 541 985 214 736

Sample Output 2

199 388 144 406 192 974

Sample Input 3

4
3278695 419852 1473646 1537928

Sample Output 3

1595840 579790 1107994 2819626

Notes

Trong ví dụ thứ nhất:

• Với ~n = 6~ ta có ~\textbf{5}~ cặp số: $$(1, 4), (2, 2), (2, 3), (3, 2), (4, 1).$$

• Với ~n = 10~ ta có ~\textbf{8}~ cặp số: $$(1, 8), (2, 6), (2, 7), (4, 5), (5, 4), (6, 2), (7, 2), (8, 1).$$

• Với ~n = 13~ ta có ~\textbf{4}~ cặp số: $$(1, 11), (5, 7), (7, 5), (11, 1).$$

Trò chơi ô ăn quan truyền thống là một trò chơi truyền thống vô cùng quen thuộc với trẻ em Việt Nam. Tuy nhiên chúng ta sẽ đi đến phiên bản khác của trò chơi nhưng cũng cực trí tuệ: trò chơi lật sỏi.

Sân chơi gồm ~n~ vị trí trống từ vị trí ~0~ đến ~n - 1~. Mỗi hiệu lệnh được đưa ra, bạn sẽ nhận được ba số nguyên ~t, A, B~. Với mọi ~A ≤ i ≤ B~, nếu ~t = 0~ thì ta đổi trạng thái của vị trí thứ ~i~. Nếu ~t = 1~, ta cần đếm xem có bao nhiêu vị trí ~i~ đang có sỏi. Hãy nhanh tay trả lời các hiệu lệnh loại ~1~ nhé!

Nếu có thể nhanh tay đếm đúng số lượng sỏi thì bạn sẽ hoá thành một con rồng cừ khôi!

Input

Dòng thứ nhất gồm ~2~ số nguyên ~n~ và ~q~ ~(1 \le n, q \le 10^5)~ là số lượng hòn sỏi và số hiệu lệnh.

~q~ dòng tiếp theo, mỗi dòng gồm ~2~ loại hiệu lệnh:

• Loại ~0~: ~0 \; A \; B~ với ~0 \le A \le B < n.~

• Loại ~1~: ~1 \; A \; B~ với ~0 \le A \le B < n.~

Output

Gồm nhiều dòng, mỗi dòng là kết quả cho từng truy vấn loại ~2~.

Scoring

Sample Input 1

4 7
1 0 3
0 1 2
1 0 1
1 0 0
0 0 3
1 0 3
1 3 3

Sample Output 1

0
1
0
2
1

Notes

Giải thích test ví dụ:

Truy vấn thứ nhất, vì chưa có hòn sỏi nào, nên đáp án là ~0~.

Sau truy vấn thứ hai, các vị trí ~1, 2~ có sỏi.

Sau truy vấn thứ ba, vì chỉ có vị trí ~1~ có sỏi nên đáp án là ~1~.

Mỗi dịp Tết đến xuân về, ai cũng náo nức nô đón chờ những điều may mắn, những điều tốt đẹp sẽ đến với cuộc sống. Tập tục xông nhà là một phong tục nhằm đón những điều tốt lành vào đầu năm mới, đây từ lâu đã là một truyền thống văn hoá lâu đời của người Việt. Để đón nhận những điều tốt đẹp trong năm mới, ta cùng xem qua dãy số như sau:

Với một dãy ~k~ số nguyên ~[B_0, . . . , B_{k - 1}]~ được coi là "đẹp" nếu như tồn tại hoán vị ~[C_0, . . . , C_{k - 1}]~ sao cho tổng xor tiền tố của dãy C tăng dần. Nói cách khác, gọi ~P_i = P_{i - 1} ⊕ C_i~. Ta có ~P_0 < P_1 < . . . < P_{k - 1}~.

Mỗi ngôi nhà sẽ có một dãy số ~A~ gồm ~n~ số nguyên đại diện. Năm mới bạn muốn xông nhà cho người thân quen của mình, với mỗi ngôi nhà của gia chủ, hãy tìm xem mọi tiền tố của ~A~ có phải dãy "đẹp" không nhé. Nếu mọi prefix ~A~ đều là dãy đẹp, bạn vô cùng hợp tuổi với gia chủ đấy.

Input

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

Dòng thứ hai gồm ~n~ số nguyên dương của ngôi nhà thứ ~i~. (~1 \le A_i < 2^{30}~).

Output

Gồm ~n~ dòng, trong đó dòng thứ ~i~ sẽ trả lời cho câu hỏi ~i~ số đầu tiên trong dãy có tạo ra được dãy "đẹp" hay không. Nếu có thì in ra YES và ngược lại thì in NO.

Scoring

Sample Input 1

5
3 1 4 1 5

Sample Output 1

YES
YES
YES
YES
NO

Notes

Giải thích test ví dụ:

Dãy gồm một số đầu tiên là ~[3]~. In ra YES.

Dãy gồm hai số đầu tiên là ~[3, 1]~. Hoán vị ~[1, 3]~ thoả mãn. Do đó in ra YES.

Dãy gồm ba số đầu tiên là ~[3, 1, 4]~. Hoán vị ~[1, 3, 4]~ thoả mãn. Do đó in YES.

dãy gồm bốn số đầu tiên là ~[3, 1, 4, 1]~. Hoán vị ~[1, 3, 4, 1]~ thoả mãn. Do đó in ra YES.

Dãy có năm số không tồn tại hoán vị thoả mãn. Do đó in ra NO.