Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Row GCD

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou are given two positive integer sequences $$$a_1, \ldots, a_n$$$ and $$$b_1, \ldots, b_m$$$. For each $$$j = 1, \ldots, m$$$ find the greatest common divisor of $$$a_1 + b_j, \ldots, a_n + b_j$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{18})$$$.

The third line contains $$$m$$$ integers $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_j \leq 10^{18})$$$.

Output

Print $$$m$$$ integers. The $$$j$$$-th of them should be equal to GCD$$$(a_1 + b_j, \ldots, a_n + b_j)$$$.

Example

Input

4 4 1 25 121 169 1 2 7 23

Output

2 3 8 24

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/07/2023 08:29:50 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|