두 개의 덱

바닥에 서로 다른 $n$장의 카드가 일렬로 놓여 있다. 왼쪽에서부터 $i$번째 카드를 바닥의 $i$번 카드라 하며, 이 카드에는 양의 정수 $a_i$가 쓰여 있다.

또한 당신은 서로 다른 $n$장의 카드를 손에 들고 있다. 손의 $i$번 카드에는 양의 정수 $b_i$가 쓰여 있다.

$q$번의 게임을 진행한다. $i$번째 게임에서는 바닥의 $l_i, l_i + 1, \dots, r_i$번 카드 각각의 앞에 서로 다른 손 카드 한 장씩을 놓는다.

• 한 게임에서는 같은 손 카드를 두 번 이상 사용할 수 없다. 따라서 서로 다른 $r_i - l_i + 1$장의 손 카드를 사용한다.
• 어떤 손 카드를 어떤 바닥 카드 앞에 놓을지는 자유롭게 정할 수 있다.
• 바닥 카드에 쓰인 양의 정수와 그 앞에 놓은 손 카드에 쓰인 양의 정수가 같을 때마다 $1$점을 얻는다.

게임이 끝나면 사용한 손 카드를 모두 회수하여 다시 손에 넣는다. 따라서 모든 게임은 서로 독립적이며, 이전 게임에서 사용한 손 카드를 이후의 게임에서 다시 사용할 수 있다.

각 게임에서 얻을 수 있는 최대 점수를 구하여라.

• $2 \le n \le 3 \cdot 10^5$
• $2 \le q \le 3 \cdot 10^5$
• $1 \le a_i \le n$ ($1 \le i \le n$)
• $1 \le b_i \le n$ ($1 \le i \le n$)
• $1 \le l_i \le r_i \le n$ ($1 \le i \le q$)

첫 줄에는 카드의 수 $n$과 게임의 횟수 $q$가 공백으로 구분되어 주어진다.

둘째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어진다. $a_i$는 바닥의 $i$번 카드에 쓰인 양의 정수를 나타낸다.

셋째 줄에는 $n$개의 정수 $b_1, b_2, \dots, b_n$이 공백으로 구분되어 주어진다. $b_i$는 손의 $i$번 카드에 쓰인 양의 정수를 나타낸다.

다음 $q$개의 줄 중 $i$번째 줄에는 $i$번째 게임에서 사용하는 바닥 카드의 범위를 나타내는 두 정수 $l_i$와 $r_i$가 공백으로 구분되어 주어진다.

$q$개의 줄을 출력한다.

$i$번째 줄에는 $i$번째 게임에서 얻을 수 있는 최대 점수를 출력한다.