Cho dãy số nguyên dương ~a_1, a_2, \ldots, a_n~ và hai số nguyên dương ~l, r~. Bạn được phép thực hiện thao tác sau trên dãy ~a~:

• Xét ~i, j~ với ~1 \le i \le j \le n~, nếu ~x = \gcd(a_i, a_j)~ chưa xuất hiện trong ~a~, ta sẽ thêm ~x~ vào cuối mảng ~a~.

Hãy in ra số lần tối đa có thể thực hiện thao tác trên. Ngoài ra, với mỗi ~l \le x \le r~ hãy in ra số cặp ~(i, j)~ của mảng mới thỏa mãn ~\gcd(a_i, a_j) = x~.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n, l, r~ (~1 \le n \le 3 \cdot 10^6, 1 \le l \le r \le 3 \cdot 10^6~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \ldots a_n~. (~1 \le a_i \le 3 \cdot 10^6~).

Ouput

• Dòng đầu tiên ghi ra số thao tác tối đa có thể thực hiện trên dãy.
• Dòng thứ hai in ra ~r-l+1~ số, số thứ ~x~ (~l \le x \le r~) là số cặp ~(i, j)~ trong mảng mới thỏa mãn ~\gcd(a_i, a_j) = x~.

Scoring

Sample Input 1

5 4 6
16 3 6 12 8

Sample Ouput 1

3
5 0 1

Note

• Chọn cặp ~(1, 4)~, thêm ~4~ vào cuối dãy. Dãy mới là ~16, 3, 6, 12, 8, 4~.
• Chọn cặp ~(3, 4)~, thêm ~2~ vào cuối dãy. Dãy mới là ~16, 3, 6, 12, 8, 4, 2~.
• Chọn cặp ~(16, 3)~, thêm ~1~ vào cuối dãy. Dãy mới là ~16, 3, 6, 12, 8, 4, 2, 1~.

Từ đó, thao tác nhiều nhất có thể là ~3~.

• Với ~x=4~, có các cặp ~(1, 4)~, ~(3, 6)~, ~(4, 5)~, ~(4, 6)~, ~(5, 6)~.
• Với ~x=6~, có cặp ~(3, 4)~.

Các nhà khoa học của NASA luôn theo dõi những thiên thạch có tiềm năng tiếp cận Trái Đất. So với vũ trụ rộng lớn, các thiên thạch và Trái Đất đều có thể coi là một điểm. Để đơn giản, Trái Đất được coi là gốc của hệ trục toạ độ Oxyz. Các nhà khoa học đang theo dõi ~n~ thiên thạch. Tại thời điểm 0, thiên thạch thứ ~i~ đang ở điểm (~x_i, y_i, z_i~) và di chuyển với vận tốc (~vx_i, vy_i, vz_i~). Một thiên thạch được coi là nguy hiểm nếu khoảng cách từ nó đến Trái Đất không vượt quá ~R~. Các nhà khoa học xác định được ~m~ thời điểm quan trọng. Họ cần xác định xem tại mỗi thời điểm quan trọng, có bao nhiêu thiên thạch nguy hiểm.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~R~. (~1 \le n \le 10^5; 1 \le R \le 10^6~).
• ~n~ dòng sau, mỗi dòng chứa sáu số nguyên ~x, y, z, vx, vy~ và ~vz~ (~|x|, |y|, |z| \le 10^6; |vx|, |vy|, |vz| \le 100~) cho biết vị trí tại thời điểm 0 và vận tốc của một thiên thạch.
• Dòng tiếp theo chứa số nguyên ~m~ (~1 \le m \le 10^5~).
• Sau đó là ~m~ dòng, mỗi dòng chứa một số nguyên ~t~ (~0 \le t \le 10^7~) là một thời điểm quan trọng.

Output

• Với mỗi thời điểm quan trọng, ghi ra trên một dòng một số nguyên duy nhất là số lượng thiên thạch nguy hiểm.

Example

Sample Input 1

1 1 
-2 0 0 1 0 0 
5 
0 
1 
2 
3 
4 

Sample Output 1

0 
1 
1 
1 
0

Trên hệ trục tọa độ OXY, hiện đang có ~n~ điểm được tô màu xanh, còn lại là các điểm màu đỏ.

Bạn cần thực hiện lần lượt ~q~ truy vấn, trong đó mỗi truy vấn thuộc một trong hai loại sau:

• ~1~ ~x~ ~y~ : Đổi màu của điểm ~(x,y)~. Tức là nếu trước đó nó là màu xanh thì sẽ đổi thành đỏ và ngược lại.
• ~2~ ~x~ ~y~ ~u~ ~v~: Bạn cần in ra số cách để đi từ điểm ~(x,y)~ tới điểm ~(u,v)~ mà chỉ đi qua các điểm màu xanh. Bạn chỉ có thể đi từ điểm ~(a,b)~ tới điểm ~(c,d)~ nếu nó đều có màu xanh và ~a < c~. Vì kết quả có thể rất lớn, bạn chỉ cần in nó ra theo module ~10^9 + 7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ ~(1 \le n,q \le 2 \times 10^5)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~x_i~ và ~y_i~ miêu tả điểm ~(x_i,y_i)~ ban đầu có màu xanh. Dữ liệu đảm bảo rằng ~n~ điểm này phân biệt và ~-10^9 \le x_i, y_i \le 10^9~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ miêu tả truy vấn thứ ~i~ theo một trong hai loại:
  • ~1~ ~x_i~ ~y_i~ ~(-10^9 \le x_i, y_i \le 10^9)~.
  • ~2~ ~x_i~ ~y_i~ ~u_i~ ~v_i~ - dữ liệu đảm bảo rằng đây là các điểm đang có màu xanh. ~(-10^9 \le x_i, y_i,u_i,v_i \le 10^9)~

Subtask

• Subtask ~1~: ~n,q \le 100~ ~(20\%)~
• Subtask ~2~: ~n,q \le 2000~ ~(20\%)~
• Subtask ~3~: Các điểm có tọa độ trong khoảng ~[1,10^5]~ ~(20\%)~
• Subtask ~4~: ~n,q \le 5 \times 10^4~ ~(20\%)~
• Subtask ~5~: Không giới hạn gì thêm ~(20\%)~

Output

• Với mỗi truy vấn loại ~2~, in ra kết quả tương ứng.

Example

Sample Input 1

7 9
-1 -2
-2 -1
2 0
-1 1
0 3
3 3 
-3 4
1 -8 -9 
2 2 0 2 0
2 3 3 -1 -2
1 -8 -9
2 -1 -2 3 3
1 2 2
2 -2 -1 0 3
1 -2 -1
2 -3 4 3 3

Sample Output 1

1
0
4
3
18

Explanation

• Chỉ có duy nhất một đường đi từ ~(2,0)~ tới ~(2,0)~ là không di chuyển.
• Không thể đi từ ~(3,3)~ tới ~(-1,-2)~
• Có 4 đường đi từ ~(-1, -2)~ đến ~(3, 3)~:

1. ~(-1, -2) \rightarrow (3, 3)~
2. ~(-1, -2) \rightarrow (0, 3) \rightarrow (3, 3)~
3. ~(-1, -2) \rightarrow (2, 0) \rightarrow (3, 3)~
4. ~(-1, -2) \rightarrow (0, 3) \rightarrow (2, 0) \rightarrow (3, 3)~

Chắc hẳn các bạn đều đã quen thuộc với trò chơi bốc sỏi, khởi nguồn cho trò chơi tổng Nim nổi tiếng. Vậy nên chúng ta sẽ đi tìm hiểu một biến thể khác của trò chơi này:

Multi Nim là một trò chơi hai người với ~n~ chồng đống sỏi, trong đó đống thứ ~i~ có ~a_i~ viên sỏi. Trong mỗi lượt, người chơi hiện tại có thể loại bỏ một số viên sỏi từ nhiều đống, với điều kiện là họ phải loại bỏ ít nhất một viên sỏi. Hai người chơi lần lượt chơi xen kẽ, và người thứ nhất là người chơi đầu tiên. Trò chơi kết thúc khi tất cả các đống sỏi đều trống.

Biến thể này có vẻ hơi nhàm chán, vậy nên thay vì chơi, công việc của bạn là đếm xem có bao ván chơi kết thúc ở đúng ~k~ lượt. Vì kết quả có thể rất lớn, hãy in ra theo module ~10^9+7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ miêu tả số đống sỏi và số lượng lượt chơi ~(1 \le n,k \le 5000)~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~ - số lượng sỏi ở từng đống ~(a_i \le 10^5)~.

Subtask

• Subtask ~1~: ~n = 2, 1 \le k \le 500, a_i \le 500~ ~(20\%)~
• Subtask ~2~: ~n = 2, k \le 5000~ ~(20\%)~
• Subtask ~4~: ~n \le 500, k \le 500~ ~(30\%)~
• Subtask ~5~: Không giới hạn gì thêm ~(30\%)~

Output

• In ra số cách chơi kết thúc sau đúng ~k~ lượt.

Example

Sample Input 1

2 2
1 3

Sample Output 1

6

Sample Input 1

2 8
16 27

Sample Output 1

211991876

Explanation

Ở ví dụ ~1~ có các cách như sau:

• ~[0,1]~ ~[1,2]~
• ~[0,2]~ ~[1,1]~
• ~[0,3]~ ~[1,0]~
• ~[1,0]~ ~[0,3]~
• ~[1,1]~ ~[0,2]~
• ~[1,2]~ ~[0,1]~