Truy Hồi Bit

Cho $K$ số hạng đầu và $K$ hệ số $32$-bit. Các số hạng tiếp theo được tạo bằng phép AND theo hệ số rồi XOR các kết quả. Hãy tính số hạng thứ $M$.

Input

• Dòng đầu chứa $KM$.
• Dòng hai chứa $A_1,\dots ,A_K$.
• Dòng ba chứa $C_1,\dots ,C_K$.
• Với $i>K$: $A_i=(C_1\mathrm{AND}{A}_{(i-1)})\mathrm{XOR}\cdots \mathrm{XOR}(C_K\mathrm{AND}{A}_{(i-K)})$.

Output

• In $A_M$ dưới dạng số nguyên không dấu $32$-bit.

Constraints

• $1\le K\le 100$.
• $1\le M\le 10^9$.
• $0\le A_i,C_i<2^{32}$.

Scoring

• Subtask $1$ ($50\%$): $K\le 10,M\le 1000$.
• Subtask $2$ ($50\%$): không có giới hạn bổ sung.

Example

2 4
1 2
4294967295 4294967295

1