Hôm nay là buổi học lập trình thi đấu đầu tiên của Aoi. Bài tập đầu tiên của Aoi là in ra một dãy số chỉ toàn các số giống nhau. Tuy nhiên, vì chưa thành thục, dãy số Aoi in ra không giống với yêu cầu của đề. Vì thế, cô bé muốn kiểm tra thử dãy số của mình khác biệt bao nhiêu so với một dãy số chỉ gồm các số giống nhau. Aoi gọi độ khác biệt của một dãy số a là số lượng cặp vị trí ~i~, ~j~ sao cho ~i < j~ và ~a[i] ≠ a[j]~. Sau một hồi suy nghĩ, cô đã đếm được độ khác biệt của dãy số mình in ra (đương nhiên là tính bằng tay). Thế rồi Aoi lại suy nghĩ. Một dãy số sẽ gồm nhiều đoạn liên tiếp, vậy tổng độ khác biệt của tất cả các đoạn con liên tiếp khác rỗng của một dãy số là bao nhiêu? Bài toán này là quá khó với Aoi, vì dù sao đây chỉ mới là buổi học đầu tiên của em ấy. Vì vậy, hãy giúp Aoi nhé.

INPUT

• Dòng đầu tiên là số nguyên dương ~T~ (~T ≤ 10~) là số lượng bộ test
• Dòng đầu tiên của mỗi bộ test gồm số nguyên dương ~n~, là số lượng phần tử của dãy số
• Dòng thứ hai của mỗi bộ test gồm ~n~ số nguyên dương ~a_1, a_2, ... , a_n~ (~a_i ≤ n~)

OUTPUT

• Gồm ~T~ dòng, mỗi dòng là số nguyên duy nhất, là tổng độ khác biệt của tất cả các đoạn con liên tiếp khác rỗng của dãy số của bộ test tương ứng

Ví dụ

Input 1:

3
4
1 1 2 1
4
1 2 3 4
4
1 1 1 1

Output 1:

9
15
0

Subtask 1: 25% số test thỏa ~n ≤ 10~

Subtask 2: 25% số test thỏa ~n ≤ 100~

Subtask 3: 25% số test thỏa ~n ≤ 1000~

Subtask 4: 25% số test thỏa ~n ≤ 100000~

Hôm nay, Blue được học về ước và bội. Ước của một số nguyên không âm ~a~ là ~x~ khi ~a~ chia hết cho ~x~. Bội của một số nguyên dương ~a~ là ~x~ khi ~x~ chia hết cho ~a~. Mở rộng hơn chúng ta có ước chung lớn nhất của hai số nguyên không âm ~a~ và ~b~, được ký hiệu là ~GCD(a, b)~, là số nguyên không âm lớn nhất vừa là ước của ~a~ vừa là ước của ~b~. Còn bội chung nhỏ nhất của hai số nguyên không âm ~a~ và ~b~ sẽ được ký hiệu là ~LCM(a, b)~ và là số nguyên không âm nhỏ nhất vừa chia hết cho ~a~ và chia hết cho ~b~. Sau khi liệt kê danh sách ước của một vài số, Blue nhận ra có những số mang một tính chất rất đặc biệt, đó là tổng ước chung lớn nhất và bội chung nhỏ nhất của số ước chẵn và số ước lẻ của số đó là số lẻ. Cụ thể hơn, xét số nguyên ~x~ có ~a~ ước chẵn và ~b~ ước lẻ. ~x~ là số nguyên đặc biệt khi ~GCD(a, b) + LCM(a, b)~ là số lẻ. Tuy nhiên, vì sẽ có nhiều số mà số ước của nó rất lớn, nên Blue chỉ quan tâm đến những số đặc biệt có số lượng ước bé hơn hoặc bằng ~K~. Blue muốn nhờ bạn, một lập trình viên tài năng, trả lời các câu hỏi của Blue rằng trong các số nguyên từ ~l~ tới ~r~ sẽ có bao nhiêu số đặc biệt mà có số ước bé hơn hoặc bằng ~K~.

INPUT

• Dòng đầu tiên là số nguyên dương ~K~ (~K ≤ 1000000~)
• Dòng thứ hai gồm số nguyên dương ~T~ là số câu hỏi của Blue
• ~T~ dòng tiếp theo, mỗi dòng sẽ gồm 2 số nguyên dương ~l, r~ (~l ≤ r~)

OUTPUT

• Gồm ~T~ dòng, dòng thứ ~i~ là câu trả lời cho câu hỏi thứ ~i~

Ví dụ

Input 1

4
2
3 4
5 6

Output 1

1
0

Input 2

2
2
3 4
5 6

Output 2

0
0

Giải thích:

• ~3~ có ~0~ ước chẵn và ~2~ ước lẻ {~1~, ~3~} ~⇒ GCD(0, 2) + LCM(0, 2) = 2 + 0 = 2~ là số chẵn
• ~4~ có ~2~ ước chẵn {~2~, ~4~} và ~1~ ước lẻ {~1~} ~⇒ GCD(2, 1) + LCM (2, 1) = 1 + 2 = 3~ là số lẻ
• ~5~ có ~0~ ước chẵn và ~2~ ước lẻ {~1~, ~5~} ~⇒ GCD(0, 2) + LCM(0, 2) = 2 + 0 = 2~ là số chẵn
• ~6~ có ~2~ ước chẵn {~2~, ~6~} và ~2~ ước lẻ {~1~, ~3~} ~⇒ GCD(2, 2) + LCM(2, 2) = 2 + 2 = 4~ là số chẵn

Subtask 1 : 40% số test thỏa mãn ~T ≤ 100, 1 ≤ l ≤ r ≤ 100~

Subtask 2 : 30% số test thỏa mãn ~T ≤ 100000, 1 ≤ l ≤ r ≤ 1000000~

Subtask 3 : 30% số test thỏa mãn ~T ≤ 100000, 1 ≤ l ≤ r ≤ 1000000000000~

Halloween là một lễ hội truyền thống lớn được tổ chức vào ngày 31 tháng 10 hàng năm, trước ngày Lễ Các Thánh của đạo Kitô giáo. Đây là một ngày lễ được tổ chức để đánh dấu sự kết thúc của vụ mùa thu hoạch và bắt đầu mùa đông lạnh giá, nhằm tưởng nhớ những người quá cố, gồm các vị thánh, các vị tử đạo và tất cả những người thân đã qua đời. Ngày nay, lễ hội Halloween thường được tổ chức rộng rãi trên khắp thế giới, quy mô lớn hay nhỏ tùy theo mỗi quốc gia. Các biểu tượng đặc trưng cho lễ hội này là những trái bí ngô đèn lồng, hình ảnh phù thủy ma mị, trái táo độc, những con ma quỷ máu me, ghê rợn hay những con vật báo hiệu cho cái chết như cú mèo, dơi,... Trong ngày này, mọi người thường hóa trang thành những nhân vật ma quái, xuất hiện cùng nhau dưới ánh trăng, tham dự các bữa tiệc được trang trí rùng rợn.

Một trong những hoạt động thú vị ngày Halloween đó chính là trick or treat. Trẻ con sẽ hóa trang thành những nhân vật khác nhau, sau đó gõ cửa từng nhà để xin kẹo. Trick nghĩa là: đánh lừa, trò chơi tinh ma nghịch ngợm. Treat là tiếp đón, đối xử tử tế, tiếp đãi. Câu này có nghĩa là: Nếu muốn chúng tôi không chơi xấu thì hãy đãi chúng tôi cái gì đi. Trò này xuất phát từ niềm tin của người phương Tây: trong suốt lễ hội Samhain, vị thần Druids cho rằng người chết sẽ tìm đến lừa, gây hoang mang, lo sợ và phá hoại con người. Những hồn ma đi lại ăn xin và đến nhà nào, gia chủ phải cung cấp thức ăn cho chúng.

Pan là con gái của một ông chủ nhà máy sản xuất bánh kẹo, nên nhà cô lúc nào cũng đầy kẹo. Biết được điều này, bọn trẻ con trong xóm luôn chực chờ trước sân vườn nhà cô mỗi đêm Halloween để được phát kẹo. Halloween năm nay cũng không phải là một ngoại lệ. Cô đã lập danh sách tất cả các đứa trẻ trong xóm và đánh số ứng với từng đứa một số nguyên dương riêng biệt. Mỗi đứa trẻ khi vào nhà cô sẽ cầm một tô chứa được ~x~ viên kẹo và nếu muốn chia kẹo cho nó thì cô sẽ phải đổ đầy tô. Vì sức người có hạn, nên cô dự tính sẽ chỉ phát kẹo cho đúng ~K~ đứa trẻ, và đương nhiên là tốn ít kẹo nhất có thể. Hiện tại là buổi chiều và sân vườn nhà cô đang không có đứa trẻ nào cả. Nhưng một chút nữa thôi, chúng sẽ lần lượt ùa vào. Sẽ có ~n~ thời điểm, mỗi thời điểm sẽ diễn ra một trong ba thay đổi sau:

1) Một đứa trẻ đang không ở trong vườn đi vào với một cái tô mới

2) Một đứa trẻ đang ở trong vườn rời khỏi vườn

3) Pan thay đổi ý định, hay cụ thể hơn là thay đổi số ~K~

Pan muốn biết được số kẹo mình cần phải dùng sau mỗi thay đổi. Tuy nhiên, vì có quá nhiều thay đổi nên việc tính số kẹo cần dùng sẽ khá phức tạp. Vì thế, Pan giao nhiệm vụ cho bạn - quản gia của cô ấy - tính số kẹo cần dùng sau mỗi thay đổi.

INPUT

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~K~ ( ~K ≤ n~ ), lần lượt là số lượng thay đổi và số ~K~ ban đầu
• ~n~ dòng tiếp theo sẽ là các thay đổi, sẽ có dạng là một trong ba dạng sau:

1) ~a~ ~x~ ~( 0 < a ≤ n, 0 < x ≤ 10^9)~ : đứa trẻ có số hiệu ~a~ đi vào vườn với tô chứa được ~x~ viên kẹo

2) ~-a~ ~( 0 < a ≤ n )~ : đứa trẻ có số hiệu ~a~ rời khỏi vườn

3) ~0~ ~x~ ~( 0 < x ≤ n )~ : Pan thay đổi ý định và ~K~ có giá trị mới là ~x~

Dữ liệu đảm bảo đứa trẻ chỉ vào vườn khi nó đang không ở trong vườn và chỉ ra khỏi vườn khi nó đang ở trong vườn.

OUTPUT

• Gồm ~n~ dòng, dòng thứ ~i~ là số lượng kẹo tối thiểu cần dùng sau thay đổi thứ ~i~, nếu không thể phát được thì in ra ~-1~

Ví dụ

Input 1

10 2
1 8
2 10
3 4
-1
4 7
-3
1 4
-2
-4
-1

Output 1

-1
18
12
14
11
17
11
11
-1
-1

Input 2

10 3
1 18
0 1
2 5
0 2
3 24
0 3
-2
4 6
2 9
0 2

Output 2

-1
18
5
23
23
47
-1
48
33
15

Subtask 1: 30% số test thỏa mãn ~n ≤ 1000~

Subtask 2: 30% số test thỏa mãn ~n ≤ 100000~, không có thay đổi dạng 3

Subtask 3: 20% số test thỏa mãn ~n ≤ 100000~

Subtask 4: 20% số test thỏa mãn ~n ≤ 500000~

Rabbit đã đi lạc trong rừng mất rồi! Và Tigger sẽ phải đi tìm cậu ta. Tìm kiếm một hồi lâu, Tigger dừng chân trước một con sông. Sau khi quan sát xung quanh, Tigger nhận thấy, chỉ có một cách duy nhất để qua sông đó là nhảy qua các hòn đá. Có ~n~ hòn đá xếp thẳng hàng, vuông góc giữa hai bờ sông. Hòn đá thứ ~i~ có độ cao ~h_i~. Ngoài ra, bờ sông Tigger đang đứng có một hòn đá có độ cao là ~0~ và được đánh số là ~0~. Đương nhiên, việc qua sông là vô cùng đơn giản với Tigger. Tigger muốn hành trình của mình trở nên thử thách hơn và cậu quyết định sẽ chỉ nhảy từ ô thứ ~i~ tới ô thứ ~j > i~ nếu tồn tại một số nguyên ~x > 1~ là ước chung của ~h_i~ và ~h_j~. 'Nhưng thế này thì vẫn còn dễ quá!' - Tigger nghĩ bụng. Vì thế, cậu muốn nhảy tới mỗi hòn đá bằng nhiều cách khác nhau. Hãy tính thử xem với mỗi hòn đá, có bao nhiêu cách để Tigger nhảy từ bờ sông Tigger đang đứng tới hòn đá đó nhé.

INPUT

• Dòng đầu tiên gồm một số nguyên dương ~n~ là số lượng hòn đá.
• Dòng thứ hai gồm n số nguyên dương ~h_1, h_2, ..., h_n (h_i ≤ 1000000)~ là độ cao của các hòn đá.

OUTPUT

• Gồm ~n~ số nguyên không âm, là số cách nhảy từ bờ sông Tigger đang đứng tới hòn đá thứ ~i~, vì kết quả có thể rất lớn nên hãy in ra kết quả chia lấy dư cho ~918052004~.

Ví dụ

Input 1

5
2 4 3 6 5

Output 1

1 2 1 5 1

Giải thích:

• Hòn đá thứ 1: có ~1~ cách nhảy là ~0 → 1~
• Hòn đá thứ 2: có ~2~ cách nhảy là ~0 → 1 → 2~ và ~0 → 2~
• Hòn đá thứ 3: có ~1~ cách nhảy là ~0 → 3~
• Hòn đá thứ 4: có ~5~ cách nhảy là ~0 → 1 → 2 → 4, 0 → 1 → 4, 0 → 2 → 4, 0 → 3 → 4~ và ~0 → 4~
• Hòn đá thứ 5: có ~1~ cách nhảy là ~0 → 5~

Subtask 1: 30% số test thỏa ~n ≤ 20~;

Subtask 2: 40% số test thỏa ~n ≤ 2000~;

Subtask 3: 30% số test thỏa ~n ≤ 200000~;

https://www.youtube.com/watch?v=h5aQ7Yoh3PI