Problem Statement

Let xyz denote the 3-digit integer whose digits are x, y, z from left to right.

Given a 3-digit integer abc none of whose digits is 0, find abc+bca+cab.

Constraints

• abc is a 3-digit integer abc none of whose digits is 0.

Sample Input 1

123

Sample Output 1

666

We have 123+231+312=666.

Sample Input 2

999

Sample Output 2

2997

We have 999+999+999=2997.

Problem Statement

You are given an integer N at least 100. Print the last two digits of N.

Strictly speaking, print the tens and ones digits of N in this order.

Constraints

• 100 \le N \le 999
• N is an integer.

Sample Input 1

254

Sample Output 1

54

The last two digits of 254 are 54, which should be printed.

Sample Input 2

101

Sample Output 2

01

The last two digits of 101 are 01, which should be printed.

Problem Statement

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

Problem Statement

Takahashi is developing an RPG. He has decided to write a code that checks whether two maps are equal.

We have grids A and B with H horizontal rows and W vertical columns. Each cell in the grid has a symbol # or . written on it.
The symbols written on the cell at the i-th row from the top and j-th column from the left in A and B are denoted by A_{i, j} and B_{i, j}, respectively.

The following two operations are called a vertical shift and horizontal shift.

• For each j=1, 2, \dots, W, simultaneously do the following:
  • simultaneously replace A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j} with A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}.
• For each i = 1, 2, \dots, H, simultaneously do the following:
  • simultaneously replace A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W} with A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}.

Is there a pair of non-negative integers (s, t) that satisfies the following condition? Print Yes if there is, and No otherwise.

• After applying a vertical shift s times and a horizontal shift t times, A is equal to B.

Here, A is said to be equal to B if and only if A_{i, j} = B_{i, j} for all integer pairs (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W.

Constraints

• 2 \leq H, W \leq 30
• A_{i,j} is # or ., and so is B_{i,j}.
• H and W are integers.

Sample Input 1

4 3
..#
...
.#.
...
#..
...
.#.
...

Sample Output 1

Yes

By choosing (s, t) = (2, 1), the resulting A is equal to B.
We describe the procedure when (s, t) = (2, 1) is chosen. Initially, A is as follows.

..#
...
.#.
...

We first apply a vertical shift to make A as follows.

...
.#.
...
..#

Then we apply another vertical shift to make A as follows.

.#.
...
..#
...

Finally, we apply a horizontal shift to make A as follows, which equals B.

#..
...
.#.
...

Sample Input 2

3 2
##
##
#.
..
#.
#.

Sample Output 2

No

No choice of (s, t) makes A equal B.

Sample Input 3

4 5
#####
.#...
.##..
..##.
...##
#...#
#####
...#.

Sample Output 3

Yes

Sample Input 4

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

Sample Output 4

Yes

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 N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

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

Sample Output 2

1 2 200000
1

Problem Statement

Initially, there are N sizes of slimes.
Specifically, for each 1\leq i\leq N, there are C_i slimes of size S_i.

Takahashi can repeat slime synthesis any number of times (possibly zero) in any order.
Slime synthesis is performed as follows.

• Choose two slimes of the same size. Let this size be X, and a new slime of size 2X appears. Then, the two original slimes disappear.

Takahashi wants to minimize the number of slimes. What is the minimum number of slimes he can end up with by an optimal sequence of syntheses?

Constraints

• 1\leq N\leq 10^5
• 1\leq S_i\leq 10^9
• 1\leq C_i\leq 10^9
• S_1,S_2,\ldots,S_N are all different.
• All input values are integers.

Sample Input 1

3
3 3
5 1
6 1

Sample Output 1

3

Initially, there are three slimes of size 3, one of size 5, and one of size 6.
Takahashi can perform the synthesis twice as follows:

• First, perform the synthesis by choosing two slimes of size 3. There will be one slime of size 3, one of size 5, and two of size 6.
• Next, perform the synthesis by choosing two slimes of size 6. There will be one slime of size 3, one of size 5, and one of size 12.

No matter how he repeats the synthesis from the initial state, he cannot reduce the number of slimes to 2 or less, so you should print 3.

Sample Input 2

3
1 1
2 1
3 1

Sample Output 2

3

He cannot perform the synthesis.

Sample Input 3

1
1000000000 1000000000

Sample Output 3

13

Problem Statement

Takahashi is at the origin of a two-dimensional plane.
Takahashi will repeat teleporting N times. In each teleportation, he makes one of the following moves:

• Move from the current coordinates (x,y) to (x+A,y+B)
• Move from the current coordinates (x,y) to (x+C,y+D)
• Move from the current coordinates (x,y) to (x+E,y+F)

There are obstacles on M points (X_1,Y_1),\ldots,(X_M,Y_M) on the plane; he cannot teleport to these coordinates.

How many paths are there resulting from the N teleportations? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 300
• 0 \leq M \leq 10^5
• -10^9 \leq A,B,C,D,E,F \leq 10^9
• (A,B), (C,D), and (E,F) are distinct.
• -10^9 \leq X_i,Y_i \leq 10^9
• (X_i,Y_i)\neq(0,0)
• (X_i,Y_i) are distinct.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

5

The following 5 paths are possible:

• (0,0)\to(1,1)\to(2,3)
• (0,0)\to(1,1)\to(2,4)
• (0,0)\to(1,3)\to(2,4)
• (0,0)\to(1,3)\to(2,5)
• (0,0)\to(1,3)\to(2,6)

Sample Input 2

10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

Sample Output 2

0

Sample Input 3

300 0
0 0 1 0 0 1

Sample Output 3

292172978

Problem Statement

You are given an undirected graph G with N vertices and M edges. G is simple (it has no self-loops and multiple edges) and connected.

For i = 1, 2, \ldots, M, the i-th edge is an undirected edge \lbrace u_i, v_i \rbrace connecting Vertices u_i and v_i.

Construct two spanning trees T_1 and T_2 of G that satisfy both of the two conditions below. (T_1 and T_2 do not necessarily have to be different spanning trees.)

• T_1 satisfies the following.

  If we regard T_1 as a rooted tree rooted at Vertex 1, for any edge \lbrace u, v \rbrace of G not contained in T_1, one of u and v is an ancestor of the other in T_1.

• T_2 satisfies the following.

  If we regard T_2 as a rooted tree rooted at Vertex 1, there is no edge \lbrace u, v \rbrace of G not contained in T_2 such that one of u and v is an ancestor of the other in T_2.

We can show that there always exists T_1 and T_2 that satisfy the conditions above.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace
• 1 \leq u_i, v_i \leq N
• All values in input are integers.
• The given graph is simple and connected.

Sample Input 1

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

Sample Output 1

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

In the Sample Output above, T_1 is a spanning tree of G containing 5 edges \lbrace 1, 4 \rbrace, \lbrace 4, 3 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 4, 2 \rbrace, \lbrace 6, 2 \rbrace. This T_1 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_1:

• for edge \lbrace 5, 1 \rbrace, Vertex 1 is an ancestor of 5;
• for edge \lbrace 1, 2 \rbrace, Vertex 1 is an ancestor of 2;
• for edge \lbrace 1, 6 \rbrace, Vertex 1 is an ancestor of 6.

T_2 is another spanning tree of G containing 5 edges \lbrace 1, 5 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 1, 4 \rbrace, \lbrace 2, 1 \rbrace, \lbrace 1, 6 \rbrace. This T_2 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_2:

• for edge \lbrace 4, 3 \rbrace, Vertex 4 is not an ancestor of Vertex 3, and vice versa;
• for edge \lbrace 2, 6 \rbrace, Vertex 2 is not an ancestor of Vertex 6, and vice versa;
• for edge \lbrace 4, 2 \rbrace, Vertex 4 is not an ancestor of Vertex 2, and vice versa.

Sample Input 2

4 3
3 1
1 2
1 4

Sample Output 2

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

Tree T, containing 3 edges \lbrace 1, 2\rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace, is the only spanning tree of G. Since there are no edges of G that are not contained in T, obviously this T satisfies the conditions for both T_1 and T_2.