Problem Statement

Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.

• The i-th element is between 1 and R_i, inclusive.
• The sum of all elements is a multiple of K.

Constraints

• All input values are integers.
• 1 \le N \le 8
• 2 \le K \le 10
• 1 \le R_i \le 5

Sample Input 1

3 2
2 1 3

Sample Output 1

1 1 2
2 1 1
2 1 3

There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.

Sample Input 2

1 2
1

Sample Output 2

There may be no sequences to print.
In this case, the output can be empty.

Sample Input 3

5 5
2 3 2 3 2

Sample Output 3

1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1

Problem Statement

We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.

Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:

\displaystyle{\sum_{i=1}^{k} B_i \gt X}.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

3
3 5 2
26

Sample Output 1

8

We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.

Sample Input 2

4
12 34 56 78
1000

Sample Output 2

23

Problem Statement

You are given a string S of length N consisting of 0 and 1.

You can perform the following operation any number of times (possibly zero):

• Choose an integer i satisfying 1 \leq i \leq N, and change S_i from 0 to 1, or from 1 to 0.

Your goal is to make the 1s in S form at most one interval. Find the minimum number of operations required to achieve the goal.

More precisely, the goal is to make S such that there exists a pair of integers (l,r) satisfying both of the following conditions. Find the minimum number of operations required to achieve the goal.

• 1 \leq l \leq r \leq N+1.
• S_i= 1 and l \leq i < r are equivalent for each integer i satisfying 1 \leq i \leq N.

It can be proved that the goal can always be achieved with a finite number of operations.

T test cases are given, so solve each.

Constraints

• 1 \leq T \leq 20000
• 1 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of 0 and 1.
• For each input file, the sum of N over all test cases is at most 2 \times 10^5.
• T,N are integers.

Sample Input 1

3
5
10011
10
1111111111
7
0000000

Sample Output 1

1
0
0

In the first test case, if we perform the operation to change S_1 to 0, the 1s will form one interval. Also, the initial S does not satisfy the condition. Therefore, the answer is 1.

In the second test case, there are no 0s in S, so no operations need to be performed. Therefore, the answer is 0.

In the third test case, there are no 1s in S, so no operations need to be performed. Therefore, the answer is 0.

Sample Input 2

5
2
01
10
1000010011
12
111100010011
3
111
8
00010101

Sample Output 2

0
2
3
0
2

Problem Statement

There are N kinds of coins used in the Kingdom of Atcoder: A_1-yen, A_2-yen, \ldots, A_N-yen coins.
Here, 1=A_1 < \ldots < A_N holds, and A_{i+1} is a multiple of A_i for every 1\leq i \leq N-1.

When paying for a product worth X yen using just these coins, what is the minimum total number of coins used in payment and returned as change?

Accurately, when Y is an integer at least X, find the minimum sum of the number of coins needed to represent exactly Y yen and the number of coins needed to represent exactly Y-X yen.

Constraints

• All values in input are integers.
• 1 \leq N \leq 60
• 1=A_1 < \ldots <A_N \leq 10^{18}
• A_{i+1} is a multiple of A_i for every 1\leq i \leq N-1.
• 1\leq X \leq 10^{18}

Sample Input 1

3 87
1 10 100

Sample Output 1

5

If we pay with one 100-yen coin and receive one 10-yen coin and three 1-yen coins as the change, the total number of coins will be 5.

Sample Input 2

2 49
1 7

Sample Output 2

7

It is optimal to pay with seven 7-yen coins.

Sample Input 3

10 123456789012345678
1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

Sample Output 3

233

Problem Statement

You are given a string S of length N consisting of lowercase English letters, and Q queries. Process the queries in order.

Each query is of one of the following two kinds:

• 1 x c : replace the x-th character of S by the character c.
• 2 l r : let T be the string obtained by sorting the characters of S in ascending order. Print Yes if the string consisting of the l-th through r-th characters of S is a substring of T; print No otherwise.

Constraints

• 1\leq N \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• 1 \leq Q \leq 10^5
• For each query of the first kind, 1 \leq x \leq N.
• For each query of the first kind, c is a lowercase English letter.
• For each query of the second kind, 1 \leq l \leq r \leq N.

Sample Input 1

6
abcdcf
4
2 1 3
2 2 6
1 5 e
2 2 6

Sample Output 1

Yes
No
Yes

• In the 1-st query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string abc, consisting of the 1-st through 3-rd characters of S, is a substring of T, so Yes should be printed.
• In the 2-nd query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string bcdcf, consisting of the 2-nd through 6-th characters of S, is not a substring of T, so No should be printed.
• The 3-rd query sets the 5-th character of S to e, making S abcdef.
• In the 4-th query, abcdef is the string T obtained by sorting the characters of S in ascending order. The string bcdef, consisting of the 2-nd through 6-th characters of S, is a substring of T, so Yes should be printed.