장난감 오렌지 만들기

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$개의 줄에 걸쳐 질문이 $l_i \ r_i$ 형태로 한 줄에 하나씩 주어진다.

각 질문에 대해 답을 한 줄에 하나씩 출력한다.

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

• $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$

오렌지를 만들려면 블록이 최소 두 개 필요하다. 블록 두 개의 연결 고리 색이 같으면, 그 두 블록만으로 오렌지를 만들 수 있다.