두 개의 덱

바닥에 서로 다른 $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$

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

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

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

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