Problem Statement

You are given a string S of length N consisting of 0 and 1.
Move the K-th 1-block from the beginning in S to immediately after the (K-1)-th 1-block, and print the resulting string.

It is guaranteed that S contains at least K 1-blocks.

Here is a more precise description.

• Let S_{l\ldots r} denote the substring of S from the l-th character through the r-th character.
• We define a substring S_{l\ldots r} of S to be a 1-block if it satisfies all of the following conditions:
  • S_l = S_{l+1} = \cdots = S_r = 1
  • l = 1 or S_{l-1} = 0
  • r = N or S_{r+1} = 0

• Suppose that all 1-blocks in S are S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m}, where l_1 < l_2 < \cdots < l_m.

  Then, we define the length N string T, obtained by moving the K-th 1-block to immediately after the (K-1)-th 1-block, as follows:

  • T_i = S_i for 1 \leq i \leq r_{K-1}
  • T_i = 1 for r_{K-1} + 1 \leq i \leq r_{K-1} + (r_K - l_K) + 1
  • T_i = 0 for r_{K-1} + (r_K - l_K) + 2 \leq i \leq r_K
  • T_i = S_i for r_K + 1 \leq i \leq N

Constraints

• 1 \leq N \leq 5 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 2 \leq K
• S contains at least K 1-blocks.

Sample Input 1

15 3
010011100011001

Sample Output 1

010011111000001

S has four 1-blocks: from the 2nd to the 2nd character, from the 5th to the 7th character, from the 11th to the 12th character, and from the 15th to the 15th character.

Sample Input 2

10 2
1011111111

Sample Output 2

1111111110

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

You are given a positive integer N, and an integer A_{x,y,z} for each triple of integers (x, y, z) such that 1 \leq x, y, z \leq N.

You will be given Q queries in the following format, which must be processed in order.

For the i-th query (1 \leq i \leq Q), you are given a tuple of integers (Lx_i, Rx_i, Ly_i, Ry_i, Lz_i, Rz_i) such that 1 \leq Lx_i \leq Rx_i \leq N, 1 \leq Ly_i \leq Ry_i \leq N, and 1 \leq Lz_i \leq Rz_i \leq N. Find:

\displaystyle{\sum_{x=Lx_i}^{Rx_i} \sum_{y=Ly_i}^{Ry_i} \sum_{z=Lz_i}^{Rz_i} A_{x,y,z}}.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \leq 2 \times 10^{5}
• 0 \leq A_{x,y,z} \leq 999 (1 \leq x, y, z \leq N)
• 1 \leq Lx_i \leq Rx_i \leq N (1 \leq i \leq Q)
• 1 \leq Ly_i \leq Ry_i \leq N (1 \leq i \leq Q)
• 1 \leq Lz_i \leq Rz_i \leq N (1 \leq i \leq Q)
• All input values are integers.

Sample Input 1

2
1 2
3 4
5 6
7 8
2
1 2 2 2 1 1
2 2 1 2 1 2

Sample Output 1

10
26

For the 1st query, the sought value is A_{1,2,1} + A_{2,2,1} = 3 + 7 = 10. Thus, print 10.

For the 2nd query, the sought value is A_{2,1,1} + A_{2,1,2} + A_{2,2,1} + A_{2,2,2} = 5 + 6 + 7 + 8 = 26. Thus, print 26.

Sample Input 2

3
733 857 714
956 208 257
123 719 648
840 881 245
245 112 746
306 942 694
58 870 849
13 208 789
687 906 783
8
3 3 3 3 1 1
1 3 2 3 3 3
2 2 2 3 1 1
1 3 1 1 1 1
2 3 2 3 2 3
1 2 1 1 1 2
3 3 2 2 1 3
1 2 2 3 2 3

Sample Output 2

687
3917
551
1631
5180
3311
1010
4326

Problem Statement

You are given an integer M and N pairs of integers (A_1, B_1), (A_2, B_2), \dots, (A_N, B_N).
For all i, it holds that 1 \leq A_i \lt B_i \leq M.

A sequence S is said to be a good sequence if the following conditions are satisfied:

• S is a contiguous subsequence of the sequence (1,2,3,..., M).
• For all i, S contains at least one of A_i and B_i.

Let f(k) be the number of possible good sequences of length k.
Enumerate f(1), f(2), \dots, f(M).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq M
• All values in input are integers.

Sample Input 1

3 5
1 3
1 4
2 5

Sample Output 1

0 1 3 2 1

Here is the list of all possible good sequences.

• (1,2)
• (1,2,3)
• (2,3,4)
• (3,4,5)
• (1,2,3,4)
• (2,3,4,5)
• (1,2,3,4,5)

Sample Input 2

1 2
1 2

Sample Output 2

2 1

Sample Input 3

5 9
1 5
1 7
5 6
5 8
2 6

Sample Output 3

0 0 1 2 4 4 3 2 1

Problem Statement

Find one shortest palindrome that has S as its prefix.

Constraints

• S is a string of length between 1 and 500000, inclusive, consisting of uppercase English letters.

Sample Input 1

ABC

Sample Output 1

ABCBA

ABCBA is a shortest palindrome that has S= ABC as its prefix.

Sample Input 2

Z

Sample Output 2

Z

Z is a shortest palindrome that has S= Z as its prefix.

Sample Input 3

TREE

Sample Output 3

TREERT

TREERT is a shortest palindrome that has S= TREE as its prefix.