Problem Statement

You are given a string S consisting of lowercase English letters and digits.
S is guaranteed to end with 2023.
Change the last character of S to 4 and print the modified string.

Constraints

• S is a string of length between 4 and 100, inclusive, consisting of lowercase English letters and digits.
• S ends with 2023.

Sample Input 1

hello2023

Sample Output 1

hello2024

Changing the last character of hello2023 to 4 yields hello2024.

Sample Input 2

worldtourfinals2023

Sample Output 2

worldtourfinals2024

Sample Input 3

2023

Sample Output 3

2024

S is guaranteed to end with 2023, possibly being 2023 itself.

Sample Input 4

20232023

Sample Output 4

20232024

Problem Statement

Given a positive integer N, print a string of N zeros and N+1 ones where 0 and 1 alternate.

Constraints

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

Sample Input 1

4

Sample Output 1

101010101

A string of four zeros and five ones where 0 and 1 alternate is 101010101.

Sample Input 2

1

Sample Output 2

101

Sample Input 3

10

Sample Output 3

101010101010101010101

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
• 0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
• The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
• All values in input are integers.

Sample Input 1

4
2 1 2
2 1 1
2 2 1
2 1 2

Sample Output 1

3

Sample Input 1 contains four sequences:

• Sequence 1 : (1, 2)
• Sequence 2 : (1, 1)
• Sequence 3 : (2, 1)
• Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

5
1 1
1 1
1 2
2 1 1
3 1 1 1

Sample Output 2

4

Sample Input 2 contains five sequences:

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

Sample Input 3

1
1 1

Sample Output 3

1

Problem Statement

Takahashi has an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
It is guaranteed that A is non-decreasing.

Takahashi performs M operations on this integer sequence. In the i-th operation (1\leq i\leq M), he performs the following operation:

If the sequence A contains B_i as an element, select one such element and delete it. If no such element exists, do nothing.

Note that since A is non-decreasing, the sequence after the operation is uniquely determined regardless of the choice of element, and remains non-decreasing.

Find A after performing M operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq A_i,B_i \leq 10^9
• The integer sequence A is non-decreasing.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1 3 3 5 6

Initially, A is A=(1,2,2,3,3,3,5,6).
The operations are performed as follows:

• Delete one 2 from A, and A becomes A=(1,2,3,3,3,5,6) after the operation.
• Delete one 2 from A, and A becomes A=(1,3,3,3,5,6) after the operation.
• Since A does not contain 7 as an element, do nothing. A remains A=(1,3,3,3,5,6) after the operation.
• Delete one 3 from A, and A becomes A=(1,3,3,5,6) after the operation.
• Since A does not contain 2 as an element, do nothing. A remains A=(1,3,3,5,6) after the operation.

Therefore, after all operations, A=(1,3,3,5,6), so output the elements in this order separated by spaces.

Sample Input 2

1 2
1
1 1

Sample Output 2

A becomes empty after the operations, so output nothing.

Problem Statement

Takahashi has N pairs of socks, and the i-th pair consists of two socks of color i. One day, after organizing his chest of drawers, Takahashi realized that he had lost one sock each of colors A_1, A_2, \dots, A_K, so he decided to use the remaining 2N-K socks to make \lfloor\frac{2N-K}{2}\rfloor new pairs of socks, each pair consisting of two socks. The weirdness of a pair of a sock of color i and a sock of color j is defined as |i-j|, and Takahashi wants to minimize the total weirdness.

Find the minimum possible total weirdness when making \lfloor\frac{2N-K}{2}\rfloor pairs from the remaining socks. Note that if 2N-K is odd, there will be one sock that is not included in any pair.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• 1\leq A_1 < A_2 < \dots < A_K \leq N
• All input values are integers.

Sample Input 1

4 2
1 3

Sample Output 1

2

Below, let (i,j) denote a pair of a sock of color i and a sock of color j.

There are 1, 2, 1, 2 socks of colors 1, 2, 3, 4, respectively. Creating the pairs (1,2),(2,3),(4,4) results in a total weirdness of |1-2|+|2-3|+|4-4|=2, which is the minimum.

Sample Input 2

5 1
2

Sample Output 2

0

The optimal solution is to make the pairs (1,1),(3,3),(4,4),(5,5) and leave one sock of color 2 as a surplus (not included in any pair).

Sample Input 3

8 5
1 2 4 7 8

Sample Output 3

2

Problem Statement

Takahashi has some letters. Each letter he has is A, B, or C. Initially, he has n _ A letters A, n _ B letters B, and n _ C letters C.

He can hold one contest by using one letter A, one letter C, and additionally any one letter, for a total of three letters. Specifically, he can hold AAC by using two letters A and one letter C, ABC by using one letter each of A, B, and C, and ACC by using one letter A and two letters C.

He wants to hold as many contests as possible using the letters he currently has. Find the maximum number of contests he can hold.

T test cases are given, so report the answer for each of them.

Constraints

• 1\le T\le2\times10 ^ 5
• For each test case,
  • 0\le n _ A\le10 ^ 9
  • 0\le n _ B\le10 ^ 9
  • 0\le n _ C\le10 ^ 9
• All input values are integers.

Sample Input 1

5
3 1 2
100 0 0
1000000 1000000 1000000
31 41 59
1000000000 10000 1

Sample Output 1

2
0
1000000
31
1

In the first test case, he can hold AAC once and ABC once, for a total of two contests. Therefore, output 2 on the first line.

Problem Statement

Output all length-N sequences A=(A _ 1,A _ 2,\ldots,A _ N) consisting of non-negative integers that satisfy \displaystyle\sum _ {i=1} ^ Ni\times A _ i=K, in lexicographic order from smallest to largest.

Here, you will only receive inputs such that the number of sequences satisfying the condition is at most 3\times10 ^ 5.

Constraints

• 1\le N\le 10
• 1\le K\le 2\times10 ^ 5
• The number of sequences satisfying the condition is at most 3\times10 ^ 5.
• All input values are integers.

Sample Input 1

3 8

Sample Output 1

0 1 2
0 4 0
1 2 1
2 0 2
2 3 0
3 1 1
4 2 0
5 0 1
6 1 0
8 0 0

For example, for the sequence (0,1,2) we have 0\times1+1\times2+2\times3=0+2+6=8, so it satisfies the condition. There is no sequence satisfying the condition that is lexicographically smaller than this one, so output 0 1 2 on the first line.

Including (0,1,2), ten sequences satisfy the condition. Output these in lexicographic order from smallest to largest.

Sample Input 2

1 200000

Sample Output 2

200000

Sample Input 3

8 9

Sample Output 3

0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 0 3 0 0 0 0 0
0 1 0 0 0 0 1 0
0 1 1 1 0 0 0 0
0 2 0 0 1 0 0 0
0 3 1 0 0 0 0 0
1 0 0 0 0 0 0 1
1 0 0 2 0 0 0 0
1 0 1 0 1 0 0 0
1 1 0 0 0 1 0 0
1 1 2 0 0 0 0 0
1 2 0 1 0 0 0 0
1 4 0 0 0 0 0 0
2 0 0 0 0 0 1 0
2 0 1 1 0 0 0 0
2 1 0 0 1 0 0 0
2 2 1 0 0 0 0 0
3 0 0 0 0 1 0 0
3 0 2 0 0 0 0 0
3 1 0 1 0 0 0 0
3 3 0 0 0 0 0 0
4 0 0 0 1 0 0 0
4 1 1 0 0 0 0 0
5 0 0 1 0 0 0 0
5 2 0 0 0 0 0 0
6 0 1 0 0 0 0 0
7 1 0 0 0 0 0 0
9 0 0 0 0 0 0 0

Problem Statement

There are N+1 sequences A_0, A_1, \ldots, A_{N}. A_i is defined as follows:

• A_0 is an empty sequence.
• A_i\ (1\leq i\leq N) is a sequence obtained by appending an integer y_i to the end of the sequence A_{x_i}\ (0\leq x_i\lt i).

Find the permutation P=(P_1, P_2,\ldots,P_N) of (1,2,\ldots,N) that satisfies the following condition:

• For i = 1,2,\ldots,N-1, one of the following holds:
  • A_{P_i} is lexicographically smaller than A_{P_{i+1}}.
  • A_{P_i}= A_{P_{i+1}} and P_i\lt P_{i+1}

In other words, when A_1,A_2,\ldots,A_N are arranged in lexicographical order (when there are multiple equal sequences, arrange those with smaller indices first), P is the sequence of indices that appears in that arrangement.

Constraints

• 1\leq N\leq 3\times 10^5
• 0\leq x_i\lt i
• 1\leq y_i\leq 10^9
• All input values are integers.

Sample Input 1

4
0 2
0 1
2 2
0 1

Sample Output 1

2 4 3 1

A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1), so P=(2,4,3,1).

Sample Input 2

5
0 1
0 1
0 1
0 1
0 1

Sample Output 2

1 2 3 4 5

A_1 = A_2 = A_3 = A_4 = A_5 = (1).

Sample Input 3

10
0 305186313
1 915059758
0 105282054
1 696409999
3 185928366
3 573289179
6 254538849
3 105282054
5 696409999
8 168629803

Sample Output 3

3 8 10 5 9 6 7 1 4 2

Problem Statement

You are given an integer N. Print a string S that satisfies all of the following conditions. If no such string exists, print -1.

• S is a string of length between 1 and 1000, inclusive, consisting of the characters 1, 2, 3, 4, 5, 6, 7, 8, 9, and * (multiplication symbol).
• S is a palindrome.
• The first character of S is a digit.
• The value of S when evaluated as a formula equals N.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

363

Sample Output 1

11*3*11

S = 11*3*11 satisfies the conditions in the problem statement. Another string that satisfies the conditions is S= 363.

Sample Input 2

101

Sample Output 2

-1

Note that S must not contain the digit 0.

Sample Input 3

3154625100

Sample Output 3

2*57*184481*75*2