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

Source: hackerrank | Difficulty: HARD
Tags: Matrices


Solutions:
from sys import stderr
from array import array
p = 998244353

def readints():
	return [int(fld) for fld in input().strip().split()]

def mincycshift(a, b, degree):
	if len(a) <= degree + 1:
		return 0
	sa = succdiffn(a, degree + 1)
	sb = succdiffn(b + b + b[:degree], degree + 1)
	for i in range(len(a)):
		if all((elt == sb[j + i] for (j, elt) in enumerate(sa))):
			return i
	return None

def succdiffn(a, times, p=p):
	n = nextpow2(len(a) + times - 1)
	ffta = fft(a + [0] * (n - len(a)))
	diff = [1] + [0] * (n - 2) + [-1]
	fftdiff = fft(diff)
	anslen = len(a) - times
	return ifft([aelt * pow(d, times, p) % p for (aelt, d) in zip(ffta, fftdiff)])[:anslen]

def fft(x, p=p):
	if len(x) <= 1:
		return x
	assert len(x) & -len(x) == len(x) and p % len(x) == 1
	root = pow(3, (p - 1) // len(x), p)
	return fftmany([x], root, p)[0]

def fftmany(x, root, p=p):
	n = len(x[0])
	if n == 1:
		return x
	x2 = [row[::2] for row in x] + [row[1::2] for row in x]
	x2 = fftmany(x2, root * root % p, p)
	y = []
	lx = len(x)
	for i in range(lx):
		twiddle = 1
		y0 = array('L')
		y1 = array('L')
		for (e, o) in zip(x2[i], x2[i + lx]):
			y0.append((e + twiddle * o) % p)
			y1.append((e - twiddle * o) % p)
			twiddle = twiddle * root % p
		y.append(y0 + y1)
	return y

def ifft(x, p=p):
	x = fft(x)
	invn = pow(len(x), p - 2, p)
	return [invn * x[0] % p] + [invn * y % p for y in x[:0:-1]]

def nextpow2(x):
	n = 1
	while n < x:
		n *= 2
	return n
(n, degree) = readints()
a = readints()
b = readints()
assert n == len(a) == len(b)
ans = mincycshift(a, b, degree)
print(-1 if ans is None else ans)