Đề bài

Tin Golubić, còn được biết đến với biệt danh Ngài Ảo Thuật, là một trong những ảo thuật gia trẻ tài năng nhất Varaždin. Sở trường của Tin là ảo thuật bài, và bài toán này được viết để tri ân những màn ảo thuật thực sự ấn tượng mà chúng ta đã được chứng kiến trong nhiều năm qua.

Trong màn ảo thuật này, Tin sử dụng một bộ bài gồm \(N\) lá. Trên mỗi lá bài ghi một số nguyên khác nhau từ \(1\) đến \(N\), và \(N\) là số chẵn. Tin sẽ thực hiện một chuỗi các lần xáo bài kiểu riffle. Bất cứ lúc nào, một khán giả cũng có thể hỏi: "Sau \(t\) lần xáo, số ghi trên lá bài thứ \(i\) tính từ dưới lên là bao nhiêu?" Tin sẽ lập tức trả lời chính xác.

Bí mật của màn ảo thuật là sự kết hợp giữa trí nhớ phi thường và kỹ năng điều khiển bài của Tin. Trước tiên, Tin ghi nhớ hoàn hảo trạng thái ban đầu của bộ bài, tức là biết chính xác vị trí ban đầu của từng lá.

Sau đó, Tin sử dụng một biến thể tinh tế của cách xáo riffle thông thường mà khán giả không nhận ra. Tin cầm nửa dưới của bộ bài bằng tay trái và nửa trên bằng tay phải, luôn úp các lá bài xuống, rồi lần lượt thả từng lá để tạo thành bộ bài mới trên bàn. Thay vì tùy ý thả lá dưới cùng của một trong hai tay, Tin luôn thả lá dưới cùng có số nhỏ hơn. Khi đã thả hết bài ở một tay, Tin thả toàn bộ số bài còn lại ở tay kia. Cuối cùng, Tin gom các lá đã thả lại và hoàn tất một lần xáo.

Bắt đầu từ bộ bài ban đầu, Tin liên tục áp dụng cách xáo trên lên trạng thái hiện tại của bộ bài. Mỗi lần xáo tạo ra một thứ tự mới, và lần xáo tiếp theo được thực hiện trên thứ tự đó.

Cho trạng thái ban đầu của bộ bài, hãy mô phỏng màn ảo thuật của Tin và trả lời \(Q\) câu hỏi của khán giả.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\), cách nhau bởi dấu cách. Dữ liệu bảo đảm \(N\) là số chẵn.

Dòng thứ hai chứa \(N\) số nguyên dương, là một hoán vị của tập \(\{1,2,\ldots,N\}\). Các số mô tả trạng thái ban đầu của bộ bài theo thứ tự từ dưới lên trên.

Dòng thứ \(j\) trong \(Q\) dòng tiếp theo chứa hai số nguyên \(t\) và \(i\), cách nhau bởi dấu cách \((1\le i\le N)\). Câu hỏi thứ \(j\) yêu cầu tìm số ghi trên lá bài thứ \(i\) tính từ dưới lên sau khi hoàn thành \(t\) lần xáo.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa một số nguyên dương từ \(1\) đến \(N\), là câu trả lời cho câu hỏi thứ \(j\).

Ràng buộc

Trong tất cả các subtask:

• \(2\le N\le 200\,000\).
• \(1\le Q\le 1\,000\,000\).
• \(0\le t\le 10^9\).

Phân nhóm

• Subtask 1 (10 điểm): \(N\le 1\,000\).
• Subtask 2 (40 điểm): Mọi câu hỏi có cùng giá trị \(t\).
• Subtask 3 (25 điểm): \(N,Q\le 100\,000\).
• Subtask 4 (25 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

2
2
5

6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6

2
2
5
4
3
3

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

2
3
6
1
7
5
8
4
9
10