Hoán vị

Cho hai dãy số nguyên dương \(A=\left(a_{1}, a_{2}, \ldots, a_{n}\right)\) và \(B=\left(b_{1}, b_{2}, \ldots, b_{n}\right)\) là hai hoán vị của \(1,2, \ldots, n\). Thực hiện lần lượt \(q\) thao tác, mỗi thao tác được mô tả bằng hai chỉ số \(i, j\ (1 \leq\) \(i, j \leq n)\) gồm hai công việc sau:

• Thực hiện tráo đổi hai phần tử thứ \(i\) và thứ \(j\) trong dãy \(B\).
• Tìm một dãy là hoán vị vòng của dãy \(A\) mà số lượng vị trí tương ứng khớp với dãy \(B\) là nhiều nhất, sau đó đưa ra số lượng vị trí khớp nhiều nhất tìm được. Cụ thể, tìm số nguyên không âm \(k\ (0 \leq k \leq n-1)\) để dãy \(\left(c_{1}, c_{2}, \ldots, c_{n}\right)=\left(a_{k+1}, a_{k+2}, \ldots, a_{n}, a_{1}, a_{2} \ldots, a_{k}\right)\) có số lượng vị trí \(i\ (1 \leq i \leq n)\) mà \(c_{i}=b_{i}\) là nhiều nhất.

Yêu cầu: Cho hai dãy \(A, B\) và \(q\) thao tác, với mỗi thao tác đưa ra số lượng vị trí khớp nhiều nhất tìm được.

Input

• Dòng đầu chứa hai số nguyên dương \(n, q\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) là một hoán vị của \(1,2, \ldots, n\).
• Dòng thứ ba chứa \(n\) số nguyên dương \(b_{1}, b_{2}, \ldots, b_{n}\) là một hoán vị của \(1,2, \ldots, n\).

Output

• Gồm \(q\) dòng, mỗi dòng là số lượng vị trí khớp nhiều nhất tìm được tương ứng với thao tác trong dữ liệu vào.

Example

3 2
1 2 3
1 2 3
1 3
2 3

1
3

Scoring

• Có \(40 \%\) số test của bài có \(n \leq 100 ; q \leq 100\).
• Có \(30 \%\) số test khác của bài có \(n \leq 10^{5} ; q \leq 100\).
• Có \(30 \%\) số test còn lại của bài có \(n \leq 10^{5} ; q \leq 10^{5}\).