Mofk mới được mẹ mua cho một bộ đồ chơi biến đổi các xâu nhị phân. Ở vị trí thứ ~i~ trên bộ đồ chơi được ghi một giá trị ~a_i~. Khi đưa một xâu nhị phân ~s~ độ dài ~n~ vào vị trí ~i~ của bộ đồ chơi, Mofk sẽ nhận lại được một xâu ~s' = s \oplus (s >> a_i)~. Trong đó ~>>~ là phép cyclic right shift, mỗi lần thực hiện phép biến đổi này, ta di chuyển kí tự cuối cùng của ~s~ lên đầu xâu và tất cả các kí tự còn lại dịch sang phải ~1~ đơn vị (~abcde~ ~>>~ ~2~ = ~deabc~), và ~\oplus~ là phép toán XOR.

Rất hào hứng với bộ đồ chơi mới, Mofk đem nó đi khoe với tất cả bạn bè của mình, và ngay lập tức đã rủ được ~q~ người bạn đến thử bộ đồ chơi mới của mình. Người bạn thứ ~i~ đem theo một xâu nhị phân ~s_i~ độ dài ~n~ và muốn dùng xâu của mình thử lần lượt trên các vị trí từ ~l~ đến ~r~. Để tăng sự vui vẻ, Mofk cùng các người bạn muốn đoán xem sau khi chơi xong, xâu kết quả mà người bạn thứ ~i~ nhận được sẽ như thế nào, ai đoán trúng nhiều hơn sẽ thắng.

Hòa cùng niềm vui đó, bạn hãy thử sức mình xem có thể đánh bại được Mofk không nhé.

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~m~, ~q~ lần lượt là độ dài của các xâu nhị phân, kích thước của bộ đồ chơi và số người bạn của Mofk ~(1 \leq n \leq 16, 1 \leq m \leq 10^4, 1 \leq q \leq 10^6)~.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_m~ mô tả các giá trị của từng vị trí trên bộ đồ chơi ~(0 \leq a_i < n)~.

~Q~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~x_i, l_i, r_i~ với ~x_i~ là một số nguyên ~n~ bit mô tả xâu nhị phân người bạn thứ ~i~ đem theo, ~l_i~ và ~r_i~ mô tả các vị trí mà người bạn này sẽ chơi ~(0 \leq x_i < 2^n, 1 \leq l_i \leq r_i \leq m)~.

Output

Gồm ~q~ dòng, dòng thứ ~i~ gồm một số nguyên ~n~ bit mô tả xâu nhị phân mà bạn đoán người bạn thứ ~i~ sẽ nhận được.

Scoring

• ~20\%~ số test có ~n \leq 10, m \leq 1000, q \leq 1000~.

• ~30\%~ số test khác có ~n \leq 10, m \leq 1000, q \leq 10^5~.

• ~30\%~ số test khác so ~n \leq 16, m \leq 10^4, q \leq 10^5~.

• ~20\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

15
0
0

Notes

Người bạn thứ nhất mang tới xâu ~s_1 = 0011~, sau khi chơi vị trí thứ nhất, xâu của người bạn này trở thành ~s_1' = 0011 \oplus 1100 = 1111~. Xâu này có giá trị ~15~ trong biểu diễn thập phân.

Người bạn thứ hai mang tới xâu ~s_2 = 0101~, sau khi chơi vị trí thứ nhất, xâu của người bạn này trở thành ~s_2' = 0101 \oplus 0101 = 0000~. Sau khi chơi vị trí thứ hai, xâu của người bạn này trở thành ~s_2'' = 0000 \oplus 0000 = 0000~. Xâu này có giá trị ~0~ trong biểu diễn thập phân.