Tý cần giải bài toán sau:

Trong khu bảo tồn có \(N = 2^K\) loài sinh vật, mỗi loài được đánh mã số từ 0 đến \(N-1\). Người ta phát hiện ra rằng loài mã số \(x\) là "tiền thân" của loài mã số \(y\) nếu mọi đặc điểm di truyền của \(x\) đều có trong \(y\) (viết là \(x \subseteq y\)).

Với mỗi loài \(mask\), hãy tính tổng số lượng cá thể của tất cả các loài tiền thân của nó. Nói cách khác, tính \(G[mask] = \sum_{x \subseteq mask} A[x]\).

Đầu vào:

• Dòng 1: hai số nguyên \(N, K\) (\(N = 2^K\), \(K \le 20\))
• Dòng 2: \(N\) số nguyên \(A[0..N-1]\) (\(0 \le A[i] \le 10^9\))

Đầu ra:

• Một dòng gồm \(N\) số nguyên là \(G[mask]\) cho mọi \(mask = 0..N-1\).

Ví dụ: \(N=4, K=2, A=[1,2,3,4]\) → \(G[0]=1, G[1]=1+2=3, G[2]=1+3=4, G[3]=1+2+3+4=10\).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Ràng buộc