시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 2048 MB (추가 메모리 없음)102757076.087%

문제

In mathematics, the dihedral group $D_n$ is the group of symmetries of a regular $n$-gon. Rotations and reflections are elements of $D_n$, and in fact all elements of the dihedral group can be expressed as a series of rotations and reflections. Elements of $D_n$ act on the $n$-gon by permuting its vertices. For example, consider a regular pentagon with vertices initially labeled $1$, $3$, $5$, $4$, $2$ (clockwise, starting from the top):

Applying the above three dihedral actions to the pentagon (a rotation, reflection, and then another rotation) produces the following relabelings of the pentagon's vertices:

$1, 3, 5, 4, 2 \rightarrow 2, 1, 3, 5, 4 \rightarrow 2, 4, 5, 3, 1 \rightarrow 1, 2, 4, 5, 3.$

You are given an arbitrary clockwise labeling of the vertices of a regular $n$-gon using the integers $1$ through $n$, and a second sequence to test. Determine whether it's possible to apply some series of dihedral actions to the $n$-gon so that the test sequence appears as a contiguous clockwise sequence of vertex labels on the transformed polygon.

입력

The first line of input has two integers $n$ and $m$, ($1 \leq m \leq n \leq 5 \cdot 10^{4}$) where $n$ is the number of vertices of the polygon and $m$ is the length of the sequence to be tested.

The next line contains $n$ space-separated integers $d$ ($1 \le d \le n$). This is the initial labeling of the polygon vertices. It is guaranteed that each integer from $1$ to $n$ appears exactly once.

The next line contains $m$ space-separated integers $t$ ($1 \le t \le n$). This is the sequence to be tested.

출력

Output a single integer, which is $1$ if the test sequence could appear as a contiguous sequence of vertex labels after applying some series of dihedral actions to the initial polygon, and $0$ otherwise.

예제 입력 1

3 3
1 2 3
1 3 2

예제 출력 1

1

예제 입력 2

3 1
1 2 3
1

예제 출력 2

1

예제 입력 3

4 2
1 2 3 4
1 3

예제 출력 3

0

예제 입력 4

4 4
1 2 3 4
2 3 4 1

예제 출력 4

1

예제 입력 5

4 4
1 2 3 4
3 2 1 4

예제 출력 5

1

예제 입력 6

5 3
1 3 5 4 2
2 1 3

예제 출력 6

1

예제 입력 7

5 4
1 3 5 4 2
2 1 5 3

예제 출력 7

0