시간 제한메모리 제한제출정답맞은 사람정답 비율
6 초 1024 MB2410990.000%

문제

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$

서브태스크

번호 배점 제한
1 20

$2 \le N, Q \le 1000$

2 25

이 서브태스크에 대해서는 보석을 모두 이용하여 목걸이를 만들 수 있는지만 판별하면 된다. 즉, 답이 -1인 경우 -1을 출력하고, 답이 -1이 아닌 경우 $n$ 이하의 아무 자연수나 출력해도 정답으로 인정된다.

3 55

추가 제한 조건이 없다.

예제 입력 1

4 3
1 2 3 2
2 3 1 1
1 3
1 4
2 4

예제 출력 1

1
-1
1

예제 입력 2

4 2
1 2 3 4
2 1 4 3
1 2
1 4

예제 출력 2

1
2

노트

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

출처

Contest > Orange Cup > Orange Cup H번

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.