Cho dãy ~a~ gồm ~n~ phần tử nguyên dương. Với mỗi phần tử ~i~, hãy in ra số phần tử ~j~ thỏa mãn ~a_i \& a_j = a_j~, với ~\&~ là phép AND. Nói cách khác, với mỗi phần tử ~i~, hãy in ra số phần tử ~j~ thỏa mãn ~a_j~ là ~submask~ của ~a_i~.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả số phần tử trong dãy.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ miêu tả số phần tử ~j~ thỏa mãn ~a_j~ là ~submask~ của ~a_i~.

Constraints

• ~1 \le n \le 2*10^5~.
• ~0 < a_i < 2^{16}~.

Subtasks

• Subtask ~1~: ~n \le 1000~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Sample Input 1:

5
2 3 4 5 2

Sample Output 1:

2
3
1
2
2

Cho một dãy ~a~ gồm ~2^n~ phần tử được đánh số từ ~0~ đến ~2^n-1~. Định nghĩa ~g(mask) = \max a_i, i \in mask~, tức là ~g(mask)~ là giá trị lớn nhất của các ~a_i~ sao cho ~i~ là ~submask~ của ~mask~.

Với mỗi ~mask \in [0, 2^n-1]~, hãy in ra ~g[mask]~.

Input

• Dòng đầu tiên chứa các số nguyên dương ~n~ ~(1 \le n \le 20)~
• Dòng thứ hai gồm ~2^n~ số nguyên dương, miêu tả dãy ~a_0, a_1, ..., a_{2^n-1}~. ~(a_i \le 10^6)~

Output

• In ra toàn bộ các ~mask~.

Example

Input 1

3
4 2 6 1 5 8 9 11

Output 1

4 4 6 6 5 8 9 11

Cho một dãy ~a~ gồm ~2^n~ phần tử được đánh số từ ~0~ đến ~2^n-1~. Định nghĩa ~f(mask) = \sum a_i, i \in mask~, tức là ~f(mask)~ là tổng của các ~a_i~ sao cho ~i~ là ~submask~ của ~mask~.

Với mỗi ~mask \in [0, 2^n-1]~, hãy in ra ~f[mask]~.

Input

• Dòng đầu tiên chứa các số nguyên dương ~n~ ~(1 \le n \le 20)~
• Dòng thứ hai gồm ~2^n~ số nguyên dương, miêu tả dãy ~a_0, a_1, ..., a_{2^n-1}~. ~(a_i \le 1000)~

Output

• In ra toàn bộ các ~mask~.

Example

Input 1

3
1 2 3 4 5 6 7 8

Output 1

1 3 4 10 6 14 16 36

Cho một dãy số nguyên dương ~a_0,a_1,...,a_{n-1}~.

Với mọi ~U~ thỏa mãn ~0 \le U < n~: tính tổng ~a_i \times a_j~ với mọi ~0 \le i,j < n~ và ~(i~ ~or~ ~j \le U)~.

Toán tử ~or~ ở đây biểu diễn cho phép toán nhị phân ~OR~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 2\times10^5)~ là độ dài mảng ~a~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_0,a_1,...,a_{n-1}~. ~(0 \le a_i \le 10^7)~.

Output

• In ra ~n~ số nguyên dương trên cùng một dòng duy nhất. Số thứ ~i~ là đáp án cho ~U = i-1~ khi lấy dư cho ~10^9+7~.

Ràng buộc

• Có ~30\%~ số test thỏa mãn: ~n \le 500~
• Có ~30\%~ số test thỏa mãn: ~n \le 10^4~
• Có ~40\%~ số test thỏa mãn: Không có ràng buộc gì thêm.

Ví dụ

Input 1

3
1 2 8

Output 1

1 9 89

Input 2

5
2 3 5 5 3

Output 2

4 25 70 225 246

Nội dung chính trong tiết học Tin học trên lớp của Nam ngày hôm nay là về phép toán OR. Phép toán OR (có kí hiệu là |) được định nghĩa như sau: Kết quả của phép toán OR giữa 2 số nguyên không âm ~x~ và ~y~ là một số nguyên không âm ~z~ trong đó bit thứ ~i~ trong biểu diễn nhị phân của ~z~ sẽ là 0 khi và chỉ khi bit thứ ~i~ trong biểu diễn nhị phân của ~x~ và ~y~ đồng thời bằng 0, ngược lại bit thứ ~i~ trong biểu diễn nhị phân của ~z~ là 1.

Ví dụ, ~x = 12~ có biểu diễn nhị phân là 1100, ~y = 5~ có biểu diễn nhị phân là 0101, khi đó ~x ,|, y~ có biểu diễn nhị phân là 1101, tức giá trị 13 trong hệ cơ số thập phân.

Phép toán OR có tính chất giao hoán và kết hợp: ~x ,|, y = y ,|, x~ và ~x ,|, (y ,|, z) = (x ,|, y) ,|, z~.

Để ôn tập nội dung đã học, thầy giáo ra cho cả lớp bài tập về nhà như sau: Cho ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~ và ba số nguyên ~k, L, R~. Hãy đếm xem có bao nhiêu bộ ~k~ chỉ số ~(i_1, i_2, \ldots, i_k)~ thỏa mãn đồng thời hai điều kiện:

~1 \le i_1 < i_2 < \cdots < i_k \le n~.

Đặt ~v = a_{i_1} ,|, a_{i_2} ,|, \cdots ,|, a_{i_k}~ thì ~L \le v \le R~ và ~v~ chia hết cho 3.

Gọi ~S~ là đáp số đúng cho bài tập thầy giáo ra, vì ~S~ có thể có giá trị rất lớn và để học sinh tập trung vào vấn đề chính của bài toán nên thầy giáo chỉ yêu cầu học sinh đưa ra được phần dư của ~S~ khi chia cho ~10^9 + 7~.

Yêu cầu Hãy giúp Nam xác định phần dư của ~S~ khi chia cho ~10^9 + 7~.

Dữ liệu

Vào từ đầu vào chuẩn (không phải file OR.INP):

Dòng đầu tiên chứa bốn số nguyên ~n, k, L, R~ (~1 \le k \le n \le 10^6~; ~0 \le L \le R \le 10^6~);

Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_1, a_2, \cdots, a_n~ (~a_i \le 10^6~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra đầu ra chuẩn (không phải file OR.OUT) một số nguyên duy nhất là phần dư của ~S~ khi chia cho ~10^9 + 7~.

Ràng buộc

Có 20% số test ứng với 20% số điểm của bài thỏa mãn ~n \le 20~ và ~a_i \le 200~ (~1 \le i \le n~);

Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn ~n \le 200~ và ~a_i \le 200~ (~1 \le i \le n~);

Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn ~L = R~ và ~a_i~ (~1 \le i \le n~) là lũy thừa của 2;

Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn ~L = R~;

Có 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Sample Input 1

5 2 1 7
1 2 5 6 4

Sample Output 1

4

Giải thích

Có tất cả 4 cách chọn 2 số trong 5 số thỏa mãn yêu cầu:

~a_1 ,|, a_2 = 1 ,|, 2 = 3~

~a_2 ,|, a_4 = 2 ,|, 6 = 6~

~a_2 ,|, a_5 = 2 ,|, 4 = 6~

~a_4 ,|, a_5 = 6 ,|, 4 = 6~

Tất cả các giá trị OR này đều nằm trong đoạn ~[1, 7]~ và chia hết cho 3.

Huy và Châu trong công cuộc tìm lại cảm hứng đã quyết định đào sâu về toán học, đặc biệt là phần số học. Để tìm kiếm tài liệu, hai cậu quyết định đi tới tuyển Tin Ams, và vô tình thấy được một bài toán khó như sau được viết trên bảng:

Cho mảng ~a~ gồm ~n~ phần tử nguyên dương và một số nguyên dương ~k~.

Ta đều biết các số nguyên dương đều có thể phân tích dưới dạng thừa số nguyên tố, vậy nên đỡ mất thời gian phân tích gây tổn hại máy chấm, bạn sẽ nhận được số nguyên dương ~k~ dưới dạng phân tích thừa số nguyên tố của nó. Nói cách khác, bạn sẽ nhận được hai dãy nguyên dương ~p~ và ~x~ gồm ~m~ phần tử, thỏa mãn ~p~ gồm các số nguyên tố phân biệt. Lúc này ~k = p_1^{x_1} \times p_2^{x_2} \times p_3^{x_3} \times ... \times p_m^{x_m}~.

Giả sử ~S~ là một dãy con của dãy ~a~ (bao gồm cả dãy rỗng), ta có định nghĩa sau:

• Gọi ~LCM(S)~ là bội chung nhỏ nhất của mọi phần tử thuộc ~S~. Đối với ~S = \emptyset~, giá trị này được coi là ~1~.
• Gọi ~G(S)~ là trọng số của dãy con ~S~, giá trị ~G(S) = x~ với ~x~ là số nguyên dương nhỏ nhất thỏa mãn: ~k | LCM(S) \times x~, hay ~LCM(S) \times x~ chia hết cho ~k~.

Hãy tính tổng trọng số của các dãy con ~S~ thoả mãn ~G(S) = 1~, hay nói cách khác đếm số dãy con sao cho bội chung nhỏ nhất của nó chia hết cho ~k~.

Sau khi đọc xong, hai cậu mới biết rằng hóa ra đây là một đề bài được dự định sẽ cho vào ~AMSOI~ ~Round~ ~4~. Vốn đều là những người có ước mơ được thi ~VMO~ cháy bỏng, hai cậu đã nhanh chóng tìm ra lời giải của bài toán, thậm chí còn có thể giải một yêu cầu tổng quát hơn như sau:

Thay vì chỉ tính các dãy con ~S~ có ~G(S) = 1~, nhiệm vụ của bạn là hãy tính tổng trọng số của toàn bộ dãy con trong ~S~.

Tuy nhiên, Huy lại muốn đưa nó vào đề bài chính thức, Châu lại bảo như vậy là quá khó với các bạn học sinh. Vậy nên, hai cậu quyết định thuyết phục thầy ... đưa cả hai dạng yêu cầu này vào bài. Và đó là lý do tại sao bạn lại đọc được đề của nó vào ngày hôm nay.

Để hiện thực hóa thỉnh cầu của học trò, ~mrtee~ sẽ cho bạn một tham số ~t~.

Với ~t = 1~, bạn hãy in ra kết quả của yêu cầu thứ nhất:

Hãy tính tổng trọng số của các dãy con ~S~ thoả mãn ~G(S) = 1~, hay nói cách khác đếm số dãy con sao cho bội chung nhỏ nhất của nó chia hết cho ~k~.

Với ~t = 2~, bạn hãy in ra kết quả của yêu cầu thứ hai:

Thay vì chỉ tính các dãy con ~S~ có ~G(S) = 1~, nhiệm vụ của bạn là hãy tính tổng trọng số của toàn bộ dãy con trong ~S~.

Với cả hai yêu cầu, tổng bạn cần tính đều có giá trị rất lớn, vậy nên hãy in nó ra sau khi lấy phần dư cho ~10^9+7~.

Một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu như ta có thể bỏ bớt một vài phần tử của ~a~ và giữ nguyên thứ tự của các phần tử còn lại để thu được dãy ~b~.

Hai dãy con được gọi là khác nhau nếu tồn tại một vị trí ~i~ sao cho phần tử thứ ~i~ của dãy ~a~ được bỏ đi để tạo ra dãy con thứ nhất, nhưng không được bỏ đi để tạo ra dãy con thứ hai.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n,m,t~ (~1 \le n \le 10^5; 1 \le m \le 16; 1 \le t \le 2~).
• Dòng thứ hai gồm ~m~ số nguyên dương miêu tả dãy ~p~, dữ liệu đảm bảo rằng đây đều là các số nguyên tố và chúng đôi một khác nhau (~2 \le p_i \le 10^6~).
• Dòng thứ hai gồm ~m~ số nguyên dương miêu tả dãy ~x~ ~(1 \le \sum_{i=1}^{m} x_i \le 20)~.
• Dòng cuối cùng gồm ~n~ số nguyên dương miêu tả dãy nguyên dương ~a~ (~1 \le a_i \le 10^{9}~).

Output:

• Với ~t = 1~, hãy in ra kết quả của yêu cầu thứ nhất, ngược lại với ~t = 2~ in ra kết quả của yêu cầu thứ hai. Vì kết quả có thể rất lớn nên hãy in nó ra sau khi lấy phần dư với ~10^9+7~.

Subtask:

• Subtask ~1~ (~10\%~ số điểm): ~t = 1; n \le 20; a_i \le 15; k \le 10^9~.
• Subtask ~2~ (~15\%~ số điểm): ~t = 1; n \le 50; a_i \le 15; k \le 10^9~.
• Subtask ~3~ (~20\%~ số điểm): ~t = 2; m \le 6; x_i = 1 \forall i \in [1,m]~.
• Subtask ~4~ (~25\%~ số điểm): ~t = 2; x_i = 1 \forall i \in [1,m]~.
• Subtask ~5~ (~15\%~ số điểm): ~t = 1~.
• Subtask ~6~ (~15\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3 2 1
2 3
1 1
4 9 5

Sample Output 1

2

Sample Input 2

5 2 1
3 2
2 1
4 24 17 18 3

Sample Output 2

16

Sample Input 3

3 2 2
2 3
1 1
4 9 5

Sample Output 3

24

Sample Input 4

7 2 2
3 2
2 2
4 24 17 18 3 9 6

Sample Output 4

332

Explanation

Trong ví dụ thứ nhất, có hai dãy con ~S~ có ~G(S) = 1~ là dãy ~\{1;2\}~ và dãy ~\{1;2;3\}~.

Trong ví dụ thứ hai, có ~16~ dãy thỏa mãn chia hết cho ~k = 18~.

Ở ví dụ thứ ba với ~t = 2~ ta cần trả lời câu hỏi dạng thứ hai. Do ~k = 6~, ta sẽ xét các dãy con sau:

• ~\{\emptyset\}~: Dãy rỗng có ~LCM(\emptyset) = 1~, như vậy ~G(S) = 6~
• Ba dãy con độ dài ~1~: ~\{1\}~; ~\{2\}~; ~\{3\}~ lần lượt có ~G(S)~ là ~3;2;6~.
• Ba dãy con có độ dài ~2~: ~\{1;2\}~; ~\{2;3\}~; ~\{1;3\}~ lần lượt có ~G(S)~ là ~1;2;6~.
• Dãy con ~\{1;2;3\}~ có ~G(S) = 1~.
• Tổng lại ta thu được đáp án cho toàn bộ dãy con là ~24~.