Problem Statement

In AtCoder City, N types of garbage are collected regularly. The i-th type of garbage (i=1,2,\dots,N) is collected on days when the date modulo q_i equals r_i.

Answer Q queries. In the j-th query (j=1,2,\dots,Q), given that the t_j-th type of garbage is put out on day d_j, answer the next day on which it will be collected.

Here, if the i-th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.

Constraints

• 1 \leq N \leq 100
• 0 \leq r_i < q_i \leq 10^9
• 1 \leq Q \leq 100
• 1 \leq t_j \leq N
• 1 \leq d_j \leq 10^9
• All input values are integers.

Sample Input 1

2
7 3
4 2
5
1 1
1 3
1 4
1 15
2 7

Sample Output 1

3
3
10
17
10

• 1st query: The 1st type of garbage is collected on day 3 for the first time after day 1.
• 2nd query: The 1st type of garbage is collected on day 3 for the first time after day 3.
• 3rd query: The 1st type of garbage is collected on day 10 for the first time after day 4.

Problem Statement

You are given a horizontally written text. Convert it to vertical writing, filling spaces with *.

You are given N strings S_1, S_2, \dots, S_N consisting of lowercase English letters. Let M be the maximum length of these strings.

Print M strings T_1, T_2, \dots, T_M that satisfy the following conditions:

• Each T_i consists of lowercase English letters and *.
• Each T_i does not end with *.
• For each 1 \leq i \leq N, the following holds:
  • For each 1 \leq j \leq |S_i|, the (N-i+1)-th character of T_j exists, and the concatenation of the (N-i+1)-th characters of T_1, T_2, \dots, T_{|S_i|} in this order equals S_i.
  • For each |S_i| + 1 \leq j \leq M, the (N-i+1)-th character of T_j either does not exist or is *.

Here, |S_i| denotes the length of the string S_i.

Constraints

• N is an integer between 1 and 100, inclusive.
• Each S_i is a string of lowercase English letters with length between 1 and 100, inclusive.

Sample Input 1

3
abc
de
fghi

Sample Output 1

fda
geb
h*c
i

Placing * as the 2nd character of T_3 puts the c in the correct position. On the other hand, placing * as the 2nd and 3rd characters of T_4 would make T_4 end with *, which violates the condition.

Sample Input 2

3
atcoder
beginner
contest

Sample Output 2

cba
oet
ngc
tio
end
sne
ter
*r

Problem Statement

At the entrance of AtCoder Inc., there is a special pass-code input device. The device consists of a screen displaying one string, and two buttons.

Let t be the string shown on the screen. Initially, t is the empty string. Pressing a button changes t as follows:

• Pressing button A appends 0 to the end of t.
• Pressing button B replaces every digit in t with the next digit: for digits 0 through 8 the next digit is the one whose value is larger by 1; the next digit after 9 is 0.

For example, if t is 1984 and button A is pressed, t becomes 19840; if button B is then pressed, t becomes 20951.

You are given a string S. Starting from the empty string, press the buttons zero or more times until t coincides with S. Find the minimum number of button presses required.

Constraints

• S is a string consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
• 1 \le |S| \le 5 \times 10^{5}, where |S| is the length of S.

Sample Input 1

21

Sample Output 1

4

The following sequence of presses makes t equal to 21.

1. Press button A. t becomes 0.
2. Press button B. t becomes 1.
3. Press button A. t becomes 10.
4. Press button B. t becomes 21.

It is impossible to obtain 21 with fewer than four presses, so output 4.

Sample Input 2

407

Sample Output 2

17

Sample Input 3

2025524202552420255242025524

Sample Output 3

150

Problem Statement

We define sequences S_n as follows.

• S_1 is a sequence of length 1 containing a single 1.
• S_n (n is an integer greater than or equal to 2) is a sequence obtained by concatenating S_{n-1}, n, S_{n-1} in this order.

For example, S_2 and S_3 is defined as follows.

• S_2 is a concatenation of S_1, 2, and S_1, in this order, so it is 1,2,1.
• S_3 is a concatenation of S_2, 3, and S_2, in this order, so it is 1,2,1,3,1,2,1.

Given N, print the entire sequence S_N.

Constraints

• N is an integer.
• 1 \leq N \leq 16

Sample Input 1

2

Sample Output 1

1 2 1

As described in the Problem Statement, S_2 is 1,2,1.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

4

Sample Output 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

• S_4 is a concatenation of S_3, 4, and S_3, in this order.

Problem Statement

Given a sequence of N positive integers A=(A_1,A_2,\dots,A_N), find every integer k between 1 and M (inclusive) that satisfies the following condition:

• \gcd(A_i,k)=1 for every integer i such that 1 \le i \le N.

Constraints

• All values in input are integers.
• 1 \le N,M \le 10^5
• 1 \le A_i \le 10^5

Sample Input 1

3 12
6 1 5

Sample Output 1

3
1
7
11

For example, 7 has the properties \gcd(6,7)=1,\gcd(1,7)=1,\gcd(5,7)=1, so it is included in the set of integers satisfying the requirement.
On the other hand, 9 has the property \gcd(6,9)=3, so it is not included in that set.
We have three integers between 1 and 12 that satisfy the condition: 1, 7, and 11. Be sure to print them in ascending order.