Có một mê cung dưới lòng đất gồm ~n~ căn phòng được kết nối với nhau bằng ~n - 1~ đường hầm. Các phòng có dạng hình tròn và được đánh số từ ~1~ đến ~n~. Các đường hầm nối giữa các phòng thỏa mãn các điều kiện sau:

• Mỗi đường hầm nối trực tiếp giữa hai phòng khác nhau;

• Mọi căn phòng đều có thể đi được đến tất cả các phòng còn lại thông qua các đường hầm.

Nam đang tham gia trò chơi khám phá mê cung trên. Tuy nhiên, khó khăn khi khám phá mê cung là tất cả đèn sẽ được tắt và trong quá trình khám phá người chơi không được mang theo đèn, vì vậy Nam không thể biết được mình đang ở đâu. Để hỗ trợ cho người chơi, mỗi căn phòng đều được lắp đặt một đèn laser đặt ở trung tâm căn phòng. Ban đầu, tất cả các đèn laser đều chỉ đến một đường hầm nào đó. Người chơi sẽ xuất phát ở căn phòng ~1~.

Với trí thông minh của mình, Nam đã nghĩ ra chiến lược khám phá để luôn đảm bảo đi hết được tất cả các phòng như sau:

• Khi đến một phòng bất kì (kể cả phòng đầu tiên), xoay đèn laser theo chiều kim đồng hồ cho đến khi nó lại chỉ vào một đường hầm nào đó;

• Đi theo hướng của đèn laser vào đường hầm tương ứng;

• Lặp lại quá trình trên vô tận.

Để đánh giá độ hiệu quả của chiến lược trên, Nam đưa ra ~q~ câu hỏi. Mỗi câu hỏi gồm một số nguyên ~k~. Nam cần biết chỉ số của căn phòng sau khi Nam đi qua đúng ~k~ đường hầm theo chiến lược trên.

Yêu cầu: Hãy giúp Nam trả lời tất cả các câu hỏi đặt ra.

Input

Vào từ file văn bản MAZE.INP:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ lần lượt là số căn phòng và số câu hỏi của Nam (~2 \le n \le 10^5~, ~1 \le q \le 10^5~);

• ~n~ dòng tiếp theo mô tả mê cung, dòng thứ ~i~ mô tả căn phòng thứ ~i~. Cụ thể, dòng thứ ~i~ chứa một số nguyên ~d~, theo sau đó là ~d~ số nguyên ~c_1, c_2, \ldots, c_d~, cho biết phòng thứ ~i~ được kết nối với ~d~ đường hầm và các căn phòng chúng dẫn đến, theo chiều kim đồng hồ. Ban đầu, đèn laser ở phòng ~i~ chỉ đến đường hầm dẫn đến phòng ~c_1~;

• ~q~ dòng cuối cùng mỗi dòng chứa một số nguyên ~k~ mô tả một câu hỏi (~1 \le k \le 10^{12}~).

Các số trên cùng một dòng cách nhau bởi một dấu cách.

Output

Ghi ra file văn bản MAZE.OUT:

• Gồm ~q~ dòng, dòng thứ ~i~ chứa một số nguyên duy nhất là đáp án cho câu hỏi thứ ~i~, theo thứ tự xuất hiện trong dữ liệu.

Scoring

Sample Input 1

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

Sample Output 1

3
1
3
2
3
5

Notes

Trạng thái ban đầu của mê cung như sau:

• Ban đầu người chơi ở phòng ~1~, thực hiện xoay đèn laser theo chiều kim đồng hồ, đèn laser chỉ vào đường hầm dẫn đến phòng ~3~;

• Tại phòng ~3~, xoay đèn laser chỉ vào đường hầm dẫn đến phòng ~1~;

• Tại phòng ~1~, xoay đèn laser chỉ vào đường hầm dẫn đến phòng ~3~;

• Tại phòng ~3~, xoay đèn laser chỉ vào đường hầm dẫn đến phòng ~2~;

• Tại phòng ~2~, xoay đèn laser chỉ vào đường hầm dẫn đến phòng ~3~;

• Tại phòng ~3~, xoay đèn laser chỉ vào đường hầm dẫn đến phòng ~5~;