Problem Statement

You are given a string S consisting of digits.

Remove all characters from S except for 2, and then concatenate the remaining characters in their original order to form a new string.

Constraints

• S is a string consisting of digits with length between 1 and 100, inclusive.
• S contains at least one 2.

Sample Input 1

20250222

Sample Output 1

22222

By removing 0, 5, and 0 from 20250222 and then concatenating the remaining characters in their original order, the string 22222 is obtained.

Sample Input 2

2

Sample Output 2

2

Sample Input 3

22222000111222222

Sample Output 3

22222222222

Problem Statement

You are given a string S of length N consisting of lowercase English letters.
We denote the i-th character of S by S_i.
Print the string of length 2N obtained by concatenating S_1,S_1,S_2,S_2,\dots,S_N, and S_N in this order.
For example, if S is beginner, print bbeeggiinnnneerr.

Constraints

• N is an integer such that 1 \le N \le 50.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

8
beginner

Sample Output 1

bbeeggiinnnneerr

It is the same as the example described in the problem statement.

Sample Input 2

3
aaa

Sample Output 2

aaaaaa

Problem Statement

You are given an H-by-W matrix A.
The element at the i-th row from the top and j-th column from the left of A is A_{i,j}.

Let B be a W-by-H matrix whose element at the i-th row from the top and j-th column from the left equals A_{j, i}.
That is, B is the transpose of A.

Print B.

Constraints

• 1\leq H,W \leq 10^5
• H \times W \leq 10^5
• 1 \leq A_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

4 3
1 2 3
4 5 6
7 8 9
10 11 12

Sample Output 1

1 4 7 10
2 5 8 11
3 6 9 12

For example, we have A_{2,1}=4, so the element at the 1-st row from the top and 2-nd column from the left of the transpose B is 4.

Sample Input 2

2 2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

1000000000 1000000000
1000000000 1000000000

Problem Statement

You are given N strings S_1,S_2,\dots,S_N of odd lengths consisting of lowercase English letters.

Let m be the length of the longest string among S_1,S_2,\dots,S_N. Find strings T_1,T_2,\dots,T_N satisfying the following condition.

• Condition: T_i is a string of length m formed by concatenating k copies of ., S_i, and k copies of . in this order, for some non-negative integer k.

Constraints

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

Sample Input 1

4
apple
blueberry
coconut
dragonfruit

Sample Output 1

...apple...
.blueberry.
..coconut..
dragonfruit

m=11, and T_1,T_2,T_3,T_4 satisfy the condition in the problem statement for k=3,1,2,0, respectively.

Sample Input 2

6
abc
d
efghi
jkl
mnopq
r

Sample Output 2

.abc.
..d..
efghi
.jkl.
mnopq
..r..

Problem Statement

We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

• N \geq 2
• L_i \geq 2
• The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
• 1 \leq a_{i,j} \leq 10^9
• 1 \leq X \leq 10^{18}
• All values in input are integers.

Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

2

When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.

Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

45

Note that we distinguish all balls, even with the same numbers written on them.

Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

0

There may be no way to make the product X.

Problem Statement

We have a grid with H horizontal rows and W vertical columns. (i, j) denotes the square at the i-th row from the top and j-th column from the left.
(i,j) has a character G_{i,j} written on it. G_{i,j} is U, D, L, or R.

You are initially at (1,1). You repeat the following operation until you cannot make a move.

Let (i,j) be the square you are currently at.
If G_{i,j} is U and i \neq 1, move to (i-1,j).
If G_{i,j} is D and i \neq H, move to (i+1,j).
If G_{i,j} is L and j \neq 1, move to (i,j-1).
If G_{i,j} is R and j \neq W, move to (i,j+1).
Otherwise, you cannot make a move.

Print the square you end up at when you cannot make a move.
If you indefinitely repeat moving, print -1 instead.

Constraints

• 1 \leq H, W \leq 500
• G_{i,j} is U, D, L, or R.
• H and W are integers.

Sample Input 1

2 3
RDU
LRU

Sample Output 1

1 3

You will move as (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3), ending up here, so the answer is (1, 3).

Sample Input 2

2 3
RRD
ULL

Sample Output 2

-1

You will indefinitely repeat moving as (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots, so -1 should be printed in this case.

Sample Input 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

Sample Output 3

9 5

Problem Statement

We have 2N balls. Each ball has a color represented by an integer between 1 and N (inclusive). For each of the N colors, there are exactly two balls of that color.

These balls are contained in M cylinders placed perpendicularly to the floor. Initially, the i-th cylinder (1 \leq i \leq M) contains k_i balls, the j-th of which from the top (1 \leq j \leq k_i) has the color a_{i, j}.

Your objective is to empty all M cylinders by repeating the following operation.

• Choose two different non-empty cylinders and remove the topmost ball from each of them. Here, the two balls removed must be of the same color.

Determine whether the objective is achievable.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq k_i\ (1 \leq i \leq M)
• 1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
• \sum_{i=1}^{M} k_i = 2N
• For every x\ (1 \leq x \leq N), there exists exactly two pairs of integers (i,j) such that 1 \leq i \leq M, 1 \leq j \leq k_i, and a_{i,j}=x.
• All values in input are integers.

Sample Input 1

2 2
2
1 2
2
1 2

Sample Output 1

Yes

The objective can be achieved as follows.

1. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 1.
2. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 2.

Sample Input 2

2 2
2
1 2
2
2 1

Sample Output 2

No

No operation can be done at all, which means it is impossible to achieve the objective of emptying the M cylinders.

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges (a simple graph contains no self-loop and no multi-edges).
For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i bidirectionally.

Determine whether there is a way to paint each vertex black or white to satisfy both of the following conditions, and show one such way if it exists.

• At least one vertex is painted black.
• For every i = 1, 2, \ldots, K, the following holds:
  • the minimum distance between vertex p_i and a vertex painted black is exactly d_i.

Here, the distance between vertex u and vertex v is the minimum number of edges in a path connecting u and v.

Constraints

• 1 \leq N \leq 2000
• N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace
• 1 \leq u_i, v_i \leq N
• 0 \leq K \leq N
• 1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N
• 0 \leq d_i \leq N
• The given graph is simple and connected.
• All values in the input are integers.

Sample Input 1

5 5
1 2
2 3
3 1
3 4
4 5
2
1 0
5 2

Sample Output 1

Yes
10100

One way to satisfy the conditions is to paint vertices 1, 3 black and vertices 2, 4, 5 white.
Indeed, for each i = 1, 2, 3, 4, 5, let A_i denote the minimum distance between vertex i and a vertex painted black, and we have (A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2), where A_1 = 0, A_5 = 2.

Sample Input 2

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

Sample Output 2

No

There is no way to satisfy the conditions by painting each vertex black or white, so you should print No.

Sample Input 3

1 0
0

Sample Output 3

Yes
1

Problem Statement

You are given a string S = S_1 S_2 S_3 \dots S_{|S|} consisting of uppercase and lowercase English letters, (, and ).
The parentheses in the string S are properly matched.

Repeat the following operation until no more operations can be performed:

• First, select one pair of integers (l, r) that satisfies all of the following conditions:
  • l < r
  • S_l = (
  • S_r = )
  • Each of the characters S_{l+1}, S_{l+2}, \dots, S_{r-1} is an uppercase or lowercase English letter.
• Let T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}.
  • Here, \overline{x} denotes the string obtained by toggling the case of each character in x (uppercase to lowercase and vice versa).
• Then, delete the l-th through r-th characters of S and insert T at the position where the deletion occurred.

Refer to the sample inputs and outputs for clarification.

It can be proved that it is possible to remove all (s and )s from the string using the above operations, and the final string is independent of how and in what order the operations are performed.
Determine the final string.

Constraints

• 1 \le |S| \le 5 \times 10^5
• S consists of uppercase and lowercase English letters, (, and ).
• The parentheses in S are properly matched.

Sample Input 1

((A)y)x

Sample Output 1

YAx

Let us perform the operations for S = ((A)y)x.

• Choose l=2 and r=4. The substring (A) is removed and replaced with a.
  • After this operation, S = (ay)x.
• Choose l=1 and r=4. The substring (ay) is removed and replaced with YA.
  • After this operation, S = YAx.

After removing the parentheses, the string becomes YAx, which should be printed.

Sample Input 2

((XYZ)n(X(y)Z))

Sample Output 2

XYZNXYZ

Let us perform the operations for S = ((XYZ)n(X(y)Z)).

• Choose l=10 and r=12. The substring (y) is removed and replaced with Y.
  • After this operation, S = ((XYZ)n(XYZ)).
• Choose l=2 and r=6. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxn(XYZ)).
• Choose l=6 and r=10. The substring (XYZ) is removed and replaced with zyx.
  • After this operation, S = (zyxnzyx).
• Choose l=1 and r=9. The substring (zyxnzyx) is removed and replaced with XYZNXYZ.
  • After this operation, S = XYZNXYZ.

After removing the parentheses, the string becomes XYZNXYZ, which should be printed.

Sample Input 3

(((()))(()))(())

Sample Output 3

The final outcome may be an empty string.

Sample Input 4

dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve

Sample Output 4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve