Hide

Problem D
Fjallamynstur

Languages en is

You have received an image of your friend who’s out hiking. You know which mountain range he’s in, but not where in that mountain range. Thus your plan is to compare the image to data on the shape of the mountain range to figure out where he is, or at least narrow down the space of possibilities.

The mountain range is given as a sequence of heights, and so is the photograph. It is unknown how far from the ground the image is offset so if a sequence of numbers in the mountain range matches the photo up to a constant we consider it a match. For example if the image is given by 10 20 5 then that matches 20 30 15.

Input

The input starts with two integers $2 \leq m \leq n \leq 5 \cdot 10^5$, the length of the sequence corresponding to the photograph and the length of the sequence corresponding to the mountain range respectively. Next there is a line with $m$ integers $0 \leq p_ i \leq 10^9$, the heights of the mountain range in the photograph. Next there is a line with $m$ integers $0 \leq h_ i \leq 10^9$, the heights of the mountain range in its entirety.

Output

Print all indices $i$ such that the photograph matches the indices $i, i + 1, \dots , i + m - 1$ in increasing order with spaces separating them. If there are no such indices instead print tyndur.

Sample Input 1 Sample Output 1
3 8
5 9 13
8 12 16 12 8 4 8 12
0 5
Sample Input 2 Sample Output 2
2 8
2 2
1 2 3 4 5 6 7 8
tyndur