Bessie đang lên kế hoạch cho chuyến thám hiểm tại một vùng đấy có \(N(1 \le N \le 10^5)\) thành phố. Tại mỗi thành phố \(i\), có một cái cổng, cũng như một chu kỳ \(T_i\). Tất cả \(T_i\) đều là lũy thừa của \(2\), và \(T_1+...+T_N \le 10^5\). Nếu bạn đến cổng của thành phố \(i\) vào ngày \(t\), bạn sẽ ngay lập tức thoát ra tại cổng của thành phố \(c_{i,t \space mod \space T_i}\).

Bessie có \(Q(1 \le Q \le 5*10^4)\) kế hoạch cho chuyến đi, mỗi kế hoạch được thể hiện bởi bộ ba số \((v,t,Δ)\). Với mỗi kế hoạch, cô ấy sẽ bắt đầu tại thành phố \(v\) vào ngày \(t\). Cô ấy sẽ làm hành động sau \(Δ\) lần: Cô ấy sẽ đi theo cổng của thành phố hiện tại, sau đó đợi một ngày. Với mỗi kế hoạch, cô ấy muốn biết mình sẽ kết thúc tại thành phố nào.

Input

• Dòng đầu chứa hai số nguyên cách nhau bởi dấu cách: \(N\) - số đỉnh, và \(Q\) - số truy vấn.

• Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách: \(T_1,T_2,...,T_N(1 \le T_i, \space T_i\) là một lũy thừa của \(2\), \(T_1+...+T_N \le 10^5)\).

• Với \(i=1,2,…,N\), dòng thứ \(i+2\) chứa \(T_i\) số nguyên dương được ngăn cách bởi dấu cách: \(c_{i,0},…,c_{i,Ti−1}(1≤c_{i,t} \le N)\).

• Với \(j=1,2,…,Q\), dòng thứ \(j+N+2\) chứa ba số nguyên dương được ngăn cách bởi dấu cách: \(v_j,t_j,Δ_j(1 \le v_j \le N, \space 1 \le t_j \le 10^{18},\space 1 \le Δ_j \le 10^{18})\) của truy vấn thứ \(j\).

Output

In ra \(Q\) dòng. Dòng thứ \(j\) chứa đáp án của truy vấn thứ \(j\).

Scoring

• Subtask \(1\): \(Δ_j \le 2*10^2\).
• Subtask \(2\): \(N,\sum T_j \le 2*10^3\).
• Subtask \(3\): \(N,\sum T_j \le 10^4\).
• Subtask \(4\): Không có điểu kiện gì thêm.

Example

5 4
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 3 6
5 3 2
5 3 7

2
2
5
4

5 5
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 2 6
5 3 2
5 3 7
5 3 1000000000000000000

2
3
5
4
2