We consider two sequences of integers, $a_0,a_1,\ldots,a_{n-1}$ and $b_0,b_1,\ldots,b_{n-1}$, to be similar if there exists a polynomial, $P(x)$, with integer coefficients of a degree $\leq k$ such that $P(i)=(a_i-b_i)\ \text{mod}\ m$ (where $m=998244353$) for $0\leq i<n$.

Given sequences $\boldsymbol{a}$ and $\boldsymbol{b}$, find and print the minimal integer $\boldsymbol{x}$ (where $0\leq x<n$) such that a cyclic shift of $\boldsymbol{b}$ on $\boldsymbol{x}$ elements (sequence $\boldsymbol{b_{x}\ \text{mod}\ n\,\boldsymbol{b_{(x+1)}}\ \text{mod}\ n\,\ \cdots\boldsymbol{b_{(x+n-1)}}\ \text{mod}\ n\ \text{}$) is similar to $\boldsymbol{a}$; if no such $\boldsymbol{x}$ exists, print $-1$ instead.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the length of the sequences) and $\boldsymbol{\mbox{k}}$ (the maximum degree of polynomial).

The second line contains $n$ space-separated integers describing the respective values of $a_0,a_1,\ldots,a_{n-1}$.

The third line contains $n$ space-separated integers describing the respective values of $b_0,b_1,\ldots,b_{n-1}$.

Constraints

$1\leq n\leq10^5$
$0\leq k\leq10^9$
$0\leq a_i,b_i<m$

Output Format

Print an integer, $\boldsymbol{x}$, denoting the minimal appropriate cyclic shift. If no such value exists, print $-1$ instead.

Sample Input 0
6 0
1 2 1 2 1 2
4 3 4 3 4 3

Sample Output 0
1

Explanation 0

After a cyclic shift of $x=1$, sequence $\boldsymbol{b}$ is $[3,4,3,4,3,4]$ and $P(x)=-2$. Thus, we print $1$.

Sample Input 1
4 2
1 10 100 1000
0 0 0 0

Sample Output 1
-1

Explanation 1

Sequence $\boldsymbol{b}$ does not change after any cyclic shift and there are no integers $\boldsymbol{p}$, $\textit{q}$, and $\textbf{r}$ such that $P(x)=p\cdot x^2+q\cdot x+r$ and $P(0)=1$, $P(1)=10$, $P(2)=100$ and $P(3)=1000\:\text{mod}\:m$. Thus, we print $-1$.

见题面

见题面