Cho một dãy nhị phân vô hạn \(a₀, a₁, a₂, …\) Dãy này được sinh bởi một công thức truy hồi tuyến tính trên \(GF(2)\):

\(aᵢ = c₁aᵢ₋₁ ⊕ c₂aᵢ₋₂ ⊕ … ⊕ cₖaᵢ₋ₖ\)

Bạn được cung cấp \(2K\) phần tử đầu tiên và \(Q\) truy vấn. Với mỗi truy vấn \(Mᵢ\), hãy in ra \(aₘᵢ\).

Input

• Dòng đầu \(K, Q\).
• Dòng thứ hai xâu nhị phân \(A\) có độ dài đúng \(2K\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(Mᵢ\).

Output

• In ra \(Q\) dòng, dòng thứ \(i\) là giá trị \(aₘᵢ\).

Constraints

• \(1 ≤ K,\ Q ≤ 5000,\ 0 ≤ Mᵢ < 10¹⁸\)

Example

2 4
0110
0
1
10
11

0
1
1
1

3 5
101101
2
7
100
999
1000000000000

1
0
0
1
0