Hôm nay Nhật Huy muốn mời các em nhỏ trong xóm đến nhà mình chơi. Huy đã đi mời các em nhỏ, và biết được rằng số lượng em nhỏ sẽ đến nhà mình hôm nay sẽ không ít hơn ~l~ và không nhiều hơn ~r~.

Ở nhà Nhật Huy có ~n~ hộp kẹo, hộp kẹo thứ ~i~ có ~a_i~ viên kẹo. Sau khi tất cả các em nhỏ đã đến nhà, Huy sẽ lấy một trong ~n~ hộp kẹo ra và chia đều số kẹo cho các em nhỏ. Huy sẽ cố gắng chọn hộp kẹo sao cho tất cả các em nhỏ đều nhận được số viên kẹo bằng nhau, nhưng có những trường hợp mà Huy không thể chọn được hộp kẹo nào thỏa mãn.

Bạn hãy đếm giúp Huy số giá trị ~x~ với ~l \le x \le r~ sao cho nếu có ~x~ em nhỏ đến chơi nhà thì Huy không thể chọn được hộp kẹo nào thỏa mãn.

Dữ liệu - Nhập từ tệp văn bản NOTDIV.inp:

• Dòng đầu tiên gồm ba số nguyên dương ~n, l, r~ ~(1 \le n \le 10^4, 1 \le l \le r \le 10^6)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^6)~.

Kết quả - Ghi ra tệp văn bản NOTDIV.out:

• Một dòng duy nhất gồm số cách chia kẹo thỏa mãn.

Chấm điểm

Ví dụ

Dữ liệu (NOTDIV.inp)

4 2 7
7 8 9 10

Kết quả (NOTDIV.out)

1

Giải thích

• Nếu có ~2~ hoặc ~4~ em nhỏ đến nhà, Huy có thể chọn hộp kẹo thứ ~2~.
• Nếu có ~3~ em nhỏ đến nhà, Huy có thể chọn hộp kẹo thứ ~3~.
• Nếu có ~5~ em nhỏ đến nhà, Huy có thể chọn hộp kẹo thứ ~4~.
• Nếu có ~7~ em nhỏ đến nhà, Huy có thể chọn hộp kẹo thứ ~1~.
• Trường hợp duy nhất mà Huy không thể chọn hộp kẹo nào thỏa mãn là khi có ~6~ em nhỏ đến nhà.

Nhật Huy có ~n~ cái kẹo và muốn chia hết số kẹo này cho ba bạn Mayly, Peace và Sunny. Biết rằng:

• Mayly không muốn số lượng kẹo mình được nhận là một số chia hết cho ~2~.
• Peace không muốn số lượng kẹo mình được nhận là một số chia hết cho ~3~.
• Sunny không muốn số lượng kẹo mình được nhận là một số chia hết cho ~4~.
• Tất cả các bạn đều không muốn số lượng kẹo mình được nhận bằng với số lượng kẹo mà người khác được nhận.

Huy muốn nhờ bạn tính xem Huy có bao nhiêu cách chia kẹo thỏa mãn. Các bạn hãy tính giúp Huy nhé.

Dữ liệu - Nhập từ tệp văn bản CANDY.inp:

• Một dòng duy nhất gồm một số nguyên dương ~n~ - số kẹo mà Huy có ~(1 \le n \le 10^6)~.

Kết quả - Ghi ra tệp văn bản CANDY.out:

• Một dòng duy nhất gồm số cách chia kẹo thỏa mãn.

Chấm điểm

Ví dụ

Dữ liệu (CANDY.inp)

6

Kết quả (CANDY.out)

3

Giải thích

Có ~3~ cách chia thỏa mãn như sau:

• Cách 1: Mayly nhận được ~1~ cái kẹo, Peace nhận được ~2~ cái kẹo, Sunny nhận được ~3~ cái kẹo.
• Cách 2: Mayly nhận được ~3~ cái kẹo, Peace nhận được ~1~ cái kẹo, Sunny nhận được ~2~ cái kẹo.
• Cách 3: Mayly nhận được ~3~ cái kẹo, Peace nhận được ~2~ cái kẹo, Sunny nhận được ~1~ cái kẹo.

Huy có một dãy số gồm ~2n~ phần tử ~a_1, a_2, ..., a_{2n}~, trong đó mỗi số nguyên dương không lớn hơn ~n~ xuất hiện đúng hai lần. Huy định nghĩa khoảng cách của một vị trí ~i~ trong dãy số và một cặp phần tử cùng có giá trị ~j~ là ~D(i, j)~, được tính theo công thức:

$$D(i, j) = (|x_j - i| + 1) \times (|y_j - i| + 1)$$

trong đó ~x_j, y_j~ là hai vị trí của hai phần tử có giá trị ~j~.

Huy muốn tính xem với mỗi vị trí ~i~ thì khoảng cách gần nhất giữa ~i~ và một cặp phần tử bất kỳ là bao nhiêu, hay nói cách khác Huy muốn tìm giá trị ~D(i, j)~ nhỏ nhất với mọi ~j~. Tuy nhiên do số vị trí quá lớn nên Huy không thể tính nhanh được, các bạn hãy giúp Huy nhé.

Dữ liệu - Nhập từ tệp văn bản PAIR.inp:

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng tiếp theo gồm ~2n~ số nguyên dương ~a_1, a_2, ..., a_{2n}~ ~(1 \le a_i \le n)~.
• Dữ liệu đầu vào đảm bảo trong dãy ~a~ có đúng hai phần tử có giá trị ~i~ với mỗi ~i~ thỏa mãn ~1 \le i \le n~.

Kết quả - Ghi ra tệp văn bản PAIR.out:

• Một dòng duy nhất gồm ~2n~ số nguyên dương, số nguyên dương thứ ~i~ là khoảng cách ngắn nhất của một cặp số bất kỳ với vị trí ~i~.

Chấm điểm

Ví dụ

Dữ liệu (PAIR.inp)

2
1 2 2 1

Kết quả (PAIR.out)

4 2 2 4

Giải thích

• Cặp phần tử có giá trị ~1~ xuất hiện tại hai vị trí ~1~ và ~4~.
• Khoảng cách giữa vị trí ~1~ và cặp phần tử có giá trị ~1~ là: $$D(1, 1) = (|x_1 - 1| + 1) \times (|y_1 - 1| + 1) = (|1 - 1| + 1) \times (|4 - 1| + 1) = 4$$
• Cặp phần tử gần nhất với vị trí ~1~ và vị trí ~4~ là cặp phần tử có giá trị ~1~, với khoảng cách là ~4~.
• Cặp phần tử gần nhất với vị trí ~2~ và vị trí ~3~ là cặp phần tử có giá trị ~2~, với khoảng cách là ~2~.

Huy có một dãy số ~a_1, a_2, ..., a_n~. Huy có thể thực hiện ~k~ lần biến đổi, mỗi lần Huy có thể thay đổi một chữ số trong dãy. Huy muốn tổng các số chia hết cho ~9~ trong dãy là lớn nhất có thể. Bạn hãy tìm cách để Huy có thể biến đổi dãy số thỏa mãn yêu cầu. Lưu ý rằng sau khi biến đổi có thể có một hoặc nhiều số bắt đầu bằng chữ số ~0~.

Dữ liệu - Nhập từ tệp văn bản DIV.inp:

• Dòng đầu tiên gồm hai số nguyên dương ~n, k~ ~(1 \le n \le 2000, 0 \le k \le 10000)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

Kết quả - Ghi ra tệp văn bản DIV.out:

• Một dòng duy nhất gồm tổng các số chia hết cho ~9~ trong dãy sau khi biến đổi.

Chấm điểm

Ví dụ

Dữ liệu (DIV.inp)

4 2
28 4 20 7

Kết quả (DIV.out)

117

Giải thích

Huy có thể thay đổi chữ số cuối cùng của phần tử đầu tiên thành chữ số ~7~, sau đó thay đổi chữ số đầu tiên của phần từ thứ ba thành chữ số ~9~ để được tổng ~27 + 90 = 117~. Có thể thấy đây là tổng lớn nhất có thể tạo được.

Hôm nay, Dung muốn cho Huy một thử thách nho nhỏ về Toán học.

Dung có một dải băng dài được chia thành ~n~ ô vuông được đánh số thứ tự từ ~1~ đến ~n~ từ trái sang phải. Ban đầu, mỗi ô vuông trên băng đều ghi số ~1~. Huy có thể yêu cầu Dung thực hiện các thao tác sau:

• ~+\ i\ j\ k~: Cộng hai số ở vị trí ~i~ và ~j~, sau đó ghi kết quả vào ô ở vị trí ~k~.
• ~*\ i\ j\ k~: Nhân hai số ở vị trí ~i~ và ~j~, sau đó ghi kết quả vào ô ở vị trí ~k~.

Lưu ý, ~i, j, k~ có thể giống nhau.

Dung sẽ cho Huy một số nguyên dương ~n~. Gọi ~p_i~ là số nguyên tố thứ ~i~. Cô có 4 loại thử thách như sau:

• Loại 1: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi giá trị ~i~.
• Loại 2: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi giá trị ~p_i~.
• Loại 3: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi tổng các giá trị ~j^3~ với ~j~ là ước của ~i~. Ví dụ, ô ~4~ sẽ ghi giá trị ~1^3 + 2^3 + 4^3 = 73~.
• Loại 4: Với mọi ô từ ~2~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi lập phương tổng các giá trị ~p_j~ với ~j~ là ước nguyên tố của ~i~. Ví dụ, ô ~6~ sẽ ghi giá trị ~(p_2 + p_3)^3 = (3 + 5)^3 = 512~. Ô ~1~ cần ghi giá trị ~1~.

Để hoàn thành thử thách, Huy được phép yêu cầu Dung thực hiện thao tác biến đổi không quá ~50000~ lần.

Các bạn hãy viết chương trình giúp Huy hoàn thành thử thách nhé.

Dữ liệu - Nhập từ tệp văn bản ARRAY.inp:

• Một dòng duy nhất gồm hai số nguyên dương ~n, \theta~, với ~\theta~ là loại thử thách của Dung. ~(1 \le n \le 20000, 1 \le \theta \le 4)~

Kết quả - Ghi ra tệp văn bản ARRAY.out:

• Dòng đầu tiên gồm một số nguyên dương ~k~ là số lần Dung cần thực hiện thao tác biến đổi. ~(0 \le k \le 50000)~
• ~k~ dòng tiếp theo, mỗi dòng thuộc một trong hai dạng sau:
  • ~+\ i\ j\ k~: mô tả thao tác cộng. ~(1 \le i, j, k \le n)~
  • ~*\ i\ j\ k~: mô tả thao tác nhân. ~(1 \le i, j, k \le n)~

Chấm điểm

Ví dụ

Dữ liệu (ARRAY.inp)

2 2

Kết quả (ARRAY.out)

2
+ 1 1 1
+ 1 2 2

Giải thích

• Đầu tiên, Huy lấy giá trị của ô đầu tiên cộng với chính nó và ghi vào ô đầu tiên. Kết quả là ~1 + 1 = 2~.
• Tiếp theo, Huy lấy giá trị của ô đầu tiên cộng với giá trị của ô thứ hai và ghi vào ô thứ hai. Kết quả là ~2 + 1 = 3~.