Sequence and Queries HY

Interview

Time limit2sMemory limit1024 MB

Summary

Given a sequence A of length N, answer each query m by printing the minimum and maximum of the remainders A_i mod m, with m up to 300000.

Problem

Given a sequence $A_1$ , $A_2$ , $\cdots$ , $A_N$ of length $N$ , write a program that processes the following query.

$m$ : Print the minimum and maximum values among $A_1 \bmod m$ , $A_2 \bmod m$ , $\cdots$ , $A_N \bmod m$ . $(1 \le m \le 300\,000)$

The first line contains $N$ and $Q$ , the length of the sequence and the number of queries, separated by a space. $(1 \le N, Q \le 300\,000)$

The second line contains $N$ integers $A_1$ , $A_2$ , $\cdots$ , $A_N$ separated by spaces. $(0 \le A_i \le 300\,000)$

From the third line, $Q$ lines follow, each containing one query described above.

For each query, print the minimum and maximum values, separated by a space, on its own line.

Example 1

Input

10 6
9 55 2 4 26 37 81 16 34 46
1
5
6
7
9
12

Expected output