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 \leq n \leq 100000~; ~1 \leq R \leq 1000000)~.

~n~ dòng sau, mỗi dòng chứa sáu số nguyên ~x~, ~y~, ~z~, ~v_x~, ~v_y~ và ~v_z~ ~(|x|, |y|, |z| \leq 1000000; |v_x|, |v_y|, |v_z| \leq 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 \leq m \leq 100000)~.

Sau đó là ~m~ dòng, mỗi dòng chứa một số nguyên ~t~ ~(0 \leq t \leq 10000000)~ 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.

Sample Input

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

Sample Output

0
1
1
1
0

Đếm số cách chia các số nguyên dương từ ~1~ đến ~n~ vào hai nhóm sao cho mọi cặp hai số khác nhau thuộc cùng một nhóm có tổng không thuộc tập ~k~ số cho trước. ~k~ số này là luỹ thừa của ~2~.

Input

Gồm không quá ~10000~ test. Mỗi test bắt đầu bằng một dòng chứa ~2~ số nguyên ~n~ và ~k~ ~(1 \leq n \leq 10^{18}~; ~1 \leq k \leq 61)~. Dòng thứ hai chứa ~k~ số nguyên dương là luỹ thừa của ~2~ và không vượt quá ~2n~.

Dữ liệu kết thúc bằng một dòng chứa hai số ~0~.

Output

Với mỗi test, ghi ra số cách phân nhóm theo modulo ~1000000007~.

Sample Input

5 1
1
4 2
4 2
0 0

Sample Output

32
8

Công ti của An sắp tổ chức ba nhạc hội. Để tổ chức nhạc hội thứ ~i~ cần một sân khấu hình chữ nhật kích thước ~a_i~ ~\times~ ~b_i~. Mỗi cạnh của sân khấu phải song song với một trong hai trục toạ độ. Do thời gian diễn ra của các nhạc hội không chồng chéo lên nhau nên phần sân khấu dùng để tổ chức nhạc hội này có thể tái sử dụng cho nhạc hội khác. Hãy tính diện tích sân khấu tối thiểu mà công ti của An phải thuê.

Input

Gồm không quá ~1000~ test. Mỗi test gồm một dòng duy nhất chứa sáu số nguyên dương ~a_1~, ~b_1~, ~a_2~, ~b_2~, ~a_3~ và ~b_3~ không vượt quá ~10000~. Dữ liệu kết thúc bằng một dòng chứa sáu số ~0~.

Output

Với mỗi test, ghi ra diện tích sân khấu tối thiểu trên một dòng

Sample Input

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

Sample Output

5
7
12

Giải thích

Nhạc hội thứ nhất được tổ chức ở vùng gạch chéo. Nhạc hội thứ hai được tổ chức ở vùng có ngôi sao năm cánh.

Nhạc hội thứ ba được tổ chức ở vùng có sọc thẳng màu xanh.

Ở một thành phố, trò chơi thoát khỏi mê cung hiện đang rất phổ biến. Mê cung gồm ~n~ căn phòng nối với nhau bởi ~m~ hành lang. Ngoài ra, người ta còn bố trí thêm ~k~ cổng dịch chuyển tức thời. Giả sử có một cổng kết nối phòng ~A~ với phòng ~B~ thì ngay sau khi người chơi đi qua một hành lang để đến phòng ~A~ thì sẽ ngay lập tức bị dịch chuyển sang phòng ~B~. Từ phòng ~B~, người chơi có thể tiếp tục di chuyển theo một hành lang nối với nó. Tương tự, khi người chơi di chuyển qua một hành lang đến phòng ~B~ thì sẽ ngay lập tức bị dịch chuyển sang phòng ~A~ và phải đi tiếp qua một hành lang nối với phòng ~A~.

Người chơi được quyền chọn bắt đầu từ một phòng bất kì. Sau đó phải đi qua mỗi hành lang đúng một lần và dừng chân tại một căn phòng bất kì. An chuẩn bị đi chơi trò này và cậu ấy đã biết bản đồ mê cung. Hãy giúp An chiến thắng trò chơi.

Input

Gồm nhiều test, mỗi test bắt đầu bằng một dòng chứa ba số nguyên ~n~, ~m~ và ~k~ ~(1 \leq n~, ~m \leq 100000~; ~0 \leq k \leq 100000)~.

~m~ dòng sau mỗi dòng chứa hai số nguyên ~u~ và ~v~ ~(1 \leq u~, ~v \leq n~; ~u~ ≠ ~v)~ cho biết có hành lang nối hai phòng ~u~ và ~v~.

~k~ dòng sau mỗi dòng chứa hai số nguyên ~u~ và ~v~ ~(1 \leq u~, ~v \leq n~; ~u~ ≠ ~v)~ cho biết có cổng dịch chuyển tức thời kết nối hai phòng ~u~ và ~v~. Mỗi phòng có cổng kết nối tức thời kết nối với tối đa một phòng khác.

Tổng ~n~, tổng ~m~ và tổng ~k~ trong tất cả các test không vượt quá ~100000~. Dữ liệu kết thúc bởi một dòng chứa ba số ~0~.

Output

Với mỗi test, nếu An có thể thắng trò chơi, ghi ra một dòng chứa từ Yes, sau đó là một dòng chứa ~m~ số nguyên cho biết chỉ số các hành lang mà An lần lượt đi qua. Các hành lang được đánh số từ ~1~ đến ~m~ theo thứ tự xuất hiện trong dữ liệu. Nếu An không thể thắng trò chơi, ghi ra một dòng duy nhất chứa từ No.

Sample Input

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

Sample Output

No
Yes
1 2 3
Yes
4 3 1 10 7 6 2 9 8 5

Cho ~n~ độ dài đoạn thẳng. Hãy đếm số cách chọn ra ~4~ trong số ~n~ độ dài trên để dựng ra một hình thang cân có diện tích khác ~0~.

Hai cách được cho là khác nhau, nếu có ~1~ cạnh trong cách này không là cạnh trong cách kia.

Input

Dòng đầu tiên chứa số nguyên ~t~ là số lượng test. Sau đó là ~t~ test.

Mỗi test bắt đầu bằng một dòng chứa số nguyên ~n~ ~(1 \leq n \leq 5000)~. Dòng thứ hai chứa ~n~ số nguyên dương không vượt quá ~100000000~ là độ dài các đoạn thẳng.

Tổng ~n~ trong tất cả các test không vượt quá ~5000~.

Output

Với mỗi test, ghi ra đáp số trên một dòng

Sample Input

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

Sample Output

1
15