Mít có các que tính có nhiều độ dài và màu sắc. Hôm nay học về hình tam giác nhọn, Mít đã nghĩ ra một bài toán rất độc đáo có liên quan tới tam giác nhọn và các que tính của mình. Mít chia các que tính thành ~N~ bộ, các que tính trong cùng một bộ thì có độ dài bằng nhau nhưng có màu khác nhau. Độ dài của các que tính trong hai bộ bất kì là khác nhau. Mít đố các bạn đếm xem có bao nhiêu tam giác nhọn khác nhau có thể được tạo ra từ ~N~ bộ que tính đó. Chú ý: mỗi cạnh của tam giác được chọn từ một bộ que tính khác nhau tức là sẽ không có tam giác cân và hai tam giác nhọn được gọi là giống nhau khi các cặp cạnh tương ứng bằng nhau và cùng màu, ngược lại là khác nhau.

Yêu cầu: Cho độ dài và số lượng các que tính của ~N~ bộ que tính, hãy lập trình đếm số lượng tam giác nhọn khác nhau có thể tạo ra.

Dữ liệu vào từ tệp văn bản TRIACU.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 2000)~ là số bộ que tính;
• ~N~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~L, C~ mô tả độ dài và số lượng que tính của bộ thứ ~i~ ~(1 ≤ i ≤ N~; ~\ L ≤ 10^6~; ~\ C ≤ 10^3)~.

Kết quả ghi ra tệp văn bản TRIACU.OUT:

Một số nguyên duy nhất là số lượng tam giác nhọn khác nhau.

Ràng buộc

• Có ~50\%~ số test ứng với ~N ≤ 200~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

4
3 3
4 1
5 2
6 2

Output

4

Giải thích

Có ~4~ tam giác nhọn có thể tạo ra từ bộ que tính thứ ~2, 3, 4~.

Số nguyên dương ~d~ được gọi là ước của số nguyên dương ~N~ nếu ~N~ chia hết cho ~d~. Ví dụ: các ước của ~9~ là ~1, 3~ và ~9;~ các ước của ~10~ là ~1, 2, 5~ và ~10~.

Yêu cầu: Cho hai số nguyên dương ~L~ và ~R~ ~(L ≤ R)~. Hãy tính tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~ ~(~bao gồm cả ~L~ và ~R)~.

Dữ liệu vào từ tệp văn bản SUMDIV.INP:

Gồm một dòng chứa hai số nguyên dương ~L~ và ~R~ ~(1 ≤ L ≤ R ≤ 10^9).~

Kết quả ghi ra tệp văn bản SUMDIV.OUT:

Một số nguyên duy nhất là tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~.

Ràng buộc

• Có ~20\%~ số test ứng với ~R ≤ 1000~;
• ~25\%~ số test khác ứng với ~R − L ≤ 1000~;
• ~25\%~ số test khác ứng với ~R ≤ 10^6~;
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

9 12

Output

63

Giải thích

Các số là ước của ít nhất một số trong đoạn ~[9, 12]~ là: ~1, 2, 3, 4, 5, 6, 9, 10, 11~ và ~12~ ~(7~ và ~8~ không nằm trong danh sách này vì cả ~9, 10, 11~ và ~12~ đều không chia hết cho ~7~ hoặc ~8)~.

Ta có ~1 + 2 + 3 + 4 + 5 + 6 + 9 + 10 + 11 + 12 = 63~.

Input

7 7

Output

8

Giải thích

Các số là ước của ~7~ là ~1~ và ~7~. Ta có ~1 + 7 = 8~.

Trong một tập hợp, một số được gọi là số chính trong một tập nếu số lần xuất hiện của số đó lớn hơn tổng số lần xuất hiện của các số còn lại.

Cho dãy số ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~ và ~𝑚~ yêu cầu. Với mỗi yêu cầu ~𝑙~, ~𝑟~, xác định xem trong tập hợp các số ~𝑎_𝑙, 𝑎_{𝑙+1}, … , 𝑎_𝑟~ có tồn tại số chính hay không.

Input

• Dòng đầu chứa ~2~ số nguyên dương ~𝑛, 𝑚~
• Dòng thứ ~2~ chứa ~𝑛~ số nguyên dương ~𝑎_1, 𝑎_2, … , 𝑎_𝑛~
• ~𝑚~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên dương ~𝑙, 𝑟~

Constraints

• ~𝑎_𝑖 ≤ 10^5~
• ~1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛~

Subtask

• Subtask ~1~ ~(20\%)~ : ~n,m \le 1000~
• Subtask ~2~ ~(30\%)~ : ~n,m \le 7000~
• Subtask ~3~ ~(50\%)~ : Không giới hạn gì thêm.

Output

• In ra đáp án cho mỗi truy vấn.

Sample Input 1

9 4
4 5 4 5 4 4 5 4 4
1 3
1 4
3 6
2 7

Sample Output 1

1
0
1
0

Duck vừa được tặng một món quà là một tấm bảng gồm ~m~ dòng và ~n~ cột, mỗi ô của bảng chứa một chữ cái.

Với tấm bảng vừa nhận được Duik liền nghĩ ra một trò chơi như sau, Duck sẽ xuất phát từ ô ~(1,\ 1)~ và đi đến ô ~(m,\ n)~, ở mỗi bước đi chỉ được đi sang phải hoặc xuống dưới so với ô Duck đang đứng. Khi đi qua mỗi ô Duck ghi lại chữ cái của ô đó để tạo thành một xâu ~s~ gồm ~m + n - 1~ kí tự khi đi đến ô ~(m,\ n)~.

Vì rất yêu thích món quà được tặng nên Duck quyết định sẽ thử mọi cách đi từ ô ~(1,\ 1)~ đến ô ~(m,\ n)~ và tạo ra tất cả các xâu có thể. Cuối cùng Duck nghĩ ra một công thức tính điểm như sau: với mỗi xâu ~s~, nếu có ~f(s)~ cách đi để tạo thành xâu ~s~ thì Duck sẽ được ~f(s)^2~ điểm.

Vì số lượng cách đi cũng như số lượng xâu tạo ra quá lớn khiến cho Duck không thể tự mình tính toán số điểm theo như công thức mà mình đã đề ra. Bạn hãy giúp Duck tính số điểm của mình nhé.

Input

Dòng đầu nhập hai số nguyên ~m~ và ~n~ ~(m \times n \leq 10^5)~ tương ứng là số hàng và cột của bảng.

~m~ dòng tiếp theo mỗi dòng nhập một xâu gồm ~n~ kí tự miêu tả một hàng trong bảng.

Output

Một số nguyên duy nhất là số điểm mà Duck nhận được (modulo ~10^9 + 7~).

Scoring

Subtask 1 (~30\%~): ~m,n \le 10~

Subtask 2 (~30\%~): ~m\times n \le 5000~

Subtask 3 (~40\%~): Không có điều kiện gì thêm

Sample Input 1

3 4
aaaa
aaab
abaa

Sample Output 1

34

Notes

Trong test ví dụ, Khi thử tất cả cách đi từ ô ~(1,\ 1)~ đến ô ~(m,\ n)~ sẽ tạo ra các xâu sau:

• ~3~ xâu aaaaaa

• ~4~ xâu aaaaba

• ~3~ xâu aaabaa

Số điểm nhận được là ~3^2 + 4^2 + 3^2 = 34~

Yakumo Ran rất thích làm toán, hôm nay cô nghiên cứu bài toán sau:

Cho một mảng ~a~ có ~n~ phần tử, cho ~q~ truy vấn dạng l r x, hãy đếm số lượng số có giá trị ~x~ trong đoạn ~a[l...r]~.

Hiện tại cô chưa có lời giải cho bài toán này nên nhờ các bạn giúp!

Input

• Dòng đầu tiên gồm hai số tự nhiên ~n, q \le 10^5~.
• Dòng tiếp theo là mảng ~a~ nguyên với ~1 \le a_i \le 10^9~.
• ~q~ dòng tiếp theo mỗi dòng gồm 3 số ~l_i, r_i, x_i~ là truy vấn thứ ~i~.

Output

• Với mỗi truy vấn in ra kết quả.

Sample Test

Input:

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

Output:

2
1

~ABC~ là một thầy giáo dạy toán nổi tiếng, đối với thầy, chỉ có hai loại số duy nhất là số nguyên tố và hợp số. Lớp học của thầy gồm ~n~ học sinh được đánh thứ tự từ ~1~ tới ~n~. Học sinh thứ ~i~ có mã số là ~a_i~ ~(1≤a_i≤3×10^5)~. Chú ý rằng ở đây các bạn học sinh không nhất thiết là có mã số khác nhau.

Một ngày nọ, thầy đến lớp và mang theo vô số viên kẹo. Thầy sẽ có ~q~ lượt phát kẹo, ở mỗi lượt thầy sẽ chọn một số nguyên dương ~t~ ~(1≤t≤2)~ và ba số nguyên dương ~l,r,v (1≤l≤r≤n; 1≤ v≤10^9)~. Thầy sẽ đi phát cho tất cả các bạn học sinh có số thứ tự ~i~, sao cho ~i∈[l,r]~, đúng ~v~ viên kẹo mỗi bạn. Tuy nhiên, thầy bỗng thấy cách chia kẹo này không thú vị, và quyết định rằng nếu ~t=1~, thầy sẽ chỉ phát kẹo cho các bạn thỏa mãn điều kiện vừa rồi đồng thời mã số ~a_i~ của bạn ấy là số nguyên tố. Ngược lại, nếu ~t=2~, thầy sẽ chỉ đi phát kẹo cho các bạn với mã số ~a_i~ là hợp số.

Sau ~q~ lượt phát kẹo, thầy muốn biết mỗi bạn học sinh có số kẹo là bao nhiêu. Do thầy chỉ dạy toán chứ không phải tin, thầy muốn nhờ các bạn lập trình tính hộ số kẹo của từng bạn.

Lưu ý ở đây ta tạm coi ~1~ là hợp số.

Input

-Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1≤ n,q≤10^5)~; -Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,…,a_n~ miêu tả mã số học sinh từ ~1~ tới ~n~. -~q~ dòng sau, mỗi dòng gồm bốn số nguyên dương ~t,l,r,val (1 \le t \le 2; 1≤l \le r≤10^5; 1 \le val≤10^9)~.

Output

• In ra một dòng ~n~ số nguyên dương là số kẹo của từng bạn học sinh.

Subtask

• Có ~20\%~ số test tương ứng với số điểm có ~n,q \le 100~
• Có ~30\%~ số test khác tương ứng với số điểm có ~n,q \le 10^4~
• Có ~30\%~ số test còn lại tương ứng với số điểm có: ~a_i~ đều là số nguyên tố.
• Có ~20\%~ số test còn lại tương ứng với số điểm không có giới hạn gì thêm.

Ví dụ

Input 1

6 3
1 2 4 3 7 10
1 2 5 2
2 1 6 1
2 5 5 4

Output 1

1 2 1 2 2 1

Giải thích 1

Ở lượt đầu tiên, ta chỉ phát kẹo cho các học sinh trong đoạn ~[2,5]~ với mã số là số nguyên tố, đó là ba bạn thứ ~2,4,5~.

Ở lượt thứ hai, ta phát kẹo cho các bạn trong đoạn ~[1,6]~ với mã số là hợp số, đó là các vị trí ~1,3,6~.

Ở lượt thứ ba, ta không thể phát kẹo cho bạn thứ ~5~ vì mã số của bạn là ~7~, đó không phải hợp số.

Cho ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~, hãy tìm số nguyên dương ~x~ nhỏ nhất thỏa mãn: ~\text{gcd}(a_i, x) > 1~ với mọi ~1 \le i \le n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 50~).

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~2 \le a_i \le 50~).

Output

• Một dòng duy nhất chứa đáp án của bài toán.

Sample Input 1

2
3 10

Sample Output 1

6

Sample Input 2

3
6 10 12

Sample Output 2

2

Cho hai số nguyên dương ~n~ và ~m~, hãy đếm số lượng cặp số nguyên ~(a,b)~ thỏa mãn điều kiện sau:

• ~a\times b \leq m~
• ~1\leq a < b \leq n~
• ~a\times b~ là số chính phương

Input

• Dòng đầu chứa số nguyên dương ~n~ (~1 \le n \le 10^{7}~).
• Dòng thứ hai chứa số nguyên dương ~m~ (~1 \le m \le 10^{14}~).

Output

• Một số nguyên duy nhất là số lượng cặp số thỏa mãn.

Sample Input

4
4

Sample Output

1

Subtask

• ~20\%~ số test có ~n \le 3\,000~
• ~20\%~ số test tiếp theo có ~n \le 10^5, m \le 10^6~
• ~30\%~ số test tiếp theo có ~n \le 10^6~
• ~30\%~ số test còn lại không có điều kiện gì thêm

Giải thích

Cặp số duy nhất thỏa mãn là ~a=1,b=4~

Bản đồ của ~1~ khu rừng được chia thành các ô vuông bằng nhau và biểu diễn dưới dạng mặt phẳng ~Oxy~ (mỗi ô ứng với ~1~ điểm có tọa độ nguyên). Một đám cháy rừng sẽ diễn ra như sau :

• Ban đầu chỉ có ~1~ ô bị cháy.
• Sau ~1~ đơn vị thời gian, đám cháy sẽ lan sang các ô có chung đỉnh hoặc chung cạnh với các ô đang cháy.

Cho ~2~ điểm ~A(0, a)~ và ~B(b, 0)~ trên mặt phẳng, bạn cần phải đi từ ~A~ đến ~B~ sao cho mỗi bước chỉ được đi xuống hoặc sang phải. Ngoài ra bạn cần trả lời các truy vấn sau:

• Mỗi truy vấn cho ~1~ cặp số ~x, t~. Hỏi nếu có ~1~ đám cháy ở ô ~(x, x)~ và đã kéo dài ~t~ đơn vị thời gian thì có bao nhiêu cách đi từ ~A~ tới ~B~ mà không đi qua các ô bị cháy ?

Ví dụ khi có điểm ~A(0, 4)~ và ~B(4, 0)~:

Input

• Gồm ~2~ dòng chứa ~2~ số nguyên ~a~ , ~b~ (thể hiện tọa độ điểm ~A~ và ~B~ như đề bài) và số nguyên ~Q~ là số lượng truy vấn. ~(1 \le a, b \le 10^{6})~ ~(1 \le q \le 3 \times 10^{5})~
• ~Q~ dòng tiếp theo , mỗi dòng chứa ~2~ số nguyên ~x~ , ~t~ là câu hỏi cho mỗi truy vấn. ~(0 \le |x|, t \le 10^{9})~

Output

• In ra ~Q~ dòng, mỗi dòng là phần dư của kết quả truy vấn đó sau khi chia cho ~10^9+7~.

Sample Input

4 4 2
2 1
2 0

Sample Output

2 
34

Subtask

• ~20\%~ số test có ~a \times b \le 1000000~ , ~q = 1~
• ~20\%~ số test tiếp theo có ~q = 1~ và ~x \le 0~
• ~60\%~ số test còn lại không có điều kiện gì thêm