22906번 - 장난감 오렌지 만들기 서브태스크스페셜 저지

문제

17살 아기 정후는 정후가 가장 좋아하는 조립식 장난감을 가지고 놀고 있다. 정후는 조립식 장난감을 이용해 오렌지를 만들려고 한다.

정후는 $N$개의 조립식 장난감 블록을 가지고 있으며, 블록 하나는 두 개의 연결 고리를 가지고 있다. 연결 고리를 통해 두 개의 블록을 서로 이어 붙일 수 있다. 연결 고리는 총 10ドル^9$가지 색 중 하나로 칠해져 있는데, 이들에는 각각 1ドル$부터 10ドル^9$까지의 번호가 붙어 있다. $i$번 장난감 블록은 각각 $a_i$번 색의 연결 고리와 $b_i$번 색의 연결 고리를 가지고 있다. 이때 두 연결 고리의 색은 서로 다르다. 즉, $a_i \neq b_i$가 성립한다. 아래 그림은 세 장난감 블록의 예시이다.

오렌지는 동그랗기 때문에, 블록으로 오렌지를 만들기 위해서는 블록이 원형으로 연결되어 있어야 한다. 이때, 같은 색의 연결 고리만 서로 연결할 수 있다. 아래는 올바른 오렌지와 올바르지 않은 오렌지의 예시이다. 첫 번째 예시의 경우 올바른 오렌지이다. 두 번째 예시의 경우 연결 고리의 색이 서로 다르므로 연결할 수 없다. 세 번째 예시의 경우 원형으로 연결되어 있지 않으므로 올바른 오렌지가 아니다.

정후는 무슨 오렌지를 만들지 행복한 고민에 빠져 있다. 정후는 장난감 블록을 일렬로 늘어놓은 뒤, 차례로 1ドル$번에서 $N$번까지 번호를 붙였다. 정후는 인접한 몇 개의 장난감 블록으로 오렌지를 만들고자 한다. 하지만 정후는 아기이기 때문에 오렌지를 어떻게 만들어야 할지 스스로 찾아내지 못하고, 당신에게 도움을 요청하였다. 당신은 아래와 같은 종류의 질문에 답하는 프로그램을 작성하여야 한다.

• $[l_i, r_i]$ 범위에 해당하는 장난감 블록을 모두 이용하여 오렌지를 하나 이상 만들 수 있는가? (이때, 오렌지가 하나만 만들어질 필요는 없다.)
• 만약 만들 수 있다면, 만들어지는 오렌지의 최소 개수는 몇 개인가?

입력

첫 번째 줄에는 장난감 블록의 개수 $N$과 질문의 횟수 $Q$가 주어진다.

두 번째 줄에는 각 장난감 블록의 첫째 연결 고리의 색 $a_1, a_2, \cdots, a_N$이 주어진다.

세 번째 줄에는 각 장난감 블록의 둘째 연결 고리의 색 $b_1, b_2, \cdots, b_N$이 주어진다.

네 번째 줄부터 $Q$개의 줄에는 $Q$개의 질문이 $l_i \ r_i$의 형태로 주어진다.

출력

각 질문에 대해, 아래와 같이 답을 한 줄에 하나씩 출력한다.

• 만약 $[l_i, r_i]$ 범위의 장난감 블록을 이용해 오렌지를 만들 수 없다면, -1을 출력한다.
• 만약 $[l_i, r_i]$ 범위의 장난감 블록을 이용해 오렌지를 만들 수 있다면, 만들어지는 오렌지의 최소 개수를 출력한다.

제한

• 2ドル \le N, Q \le 5 \times 10^5$
• 1ドル \le a_i, b_i \le 10^9$
• $a_i \neq b_i$
• 1ドル \le l_i \le r_i \le N$

서브태스크

노트

오렌지를 만들기 위해 필요한 장난감 블록의 개수는 최소 두 개이다. 장난감 블록 두 개의 연결고리 색이 서로 같은 경우, 두 장난감 블록을 통해서 오렌지를 만들 수 있다.