Problem Statement

You are given a string S consisting of uppercase English letters. Separate each character of S with a space and print them one by one in order.

Constraints

• S is a string consisting of uppercase English letters with a length between 2 and 100, inclusive.

Sample Input 1

ABC

Sample Output 1

A B C

Separate A, B, and C with spaces and print them one by one.

There is no need to print a space after C.

Sample Input 2

ZZZZZZZ

Sample Output 2

Z Z Z Z Z Z Z

Sample Input 3

OOXXOO

Sample Output 3

O O X X O O

Problem Statement

We will hand out a total of K cards to N people numbered 1, 2, \ldots, N.

Beginning with Person A, we will give the cards one by one to the people in this order: A, A+1, A+2, \ldots, N, 1, 2, \ldots. Who will get the last card?

Formally, after Person x(1 \leq x < N) gets a card, Person x+1 will get a card. After Person N gets a card, Person 1 gets a card.

Constraints

• 1 \leq N,K \leq 1000
• 1 \leq A \leq N
• All values in input are integers.

Sample Input 1

3 3 2

Sample Output 1

1

The cards are given to Person 2, 3, 1 in this order.

Sample Input 2

1 100 1

Sample Output 2

1

Sample Input 3

3 14 2

Sample Output 3

3

Problem Statement

Takahashi generated 10 strings S_1,S_2,\dots,S_{10} as follows.

• First, let S_i (1 \le i \le 10)= .......... (10 .s in a row).
• Next, choose four integers A, B, C, and D satisfying all of the following.
  • 1 \le A \le B \le 10.
  • 1 \le C \le D \le 10.
• Then, for every pair of integers (i,j) satisfying all of the following, replace the j-th character of S_i with #.
  • A \le i \le B.
  • C \le j \le D.

You are given S_1,S_2,\dots,S_{10} generated as above. Find the integers A, B, C, and D Takahashi chose.
It can be proved that such integers A, B, C, and D uniquely exist (there is just one answer) under the Constraints.

Constraints

• S_1,S_2,\dots,S_{10} are strings, each of length 10, that can be generated according to the Problem Statement.

Sample Input 1

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

Sample Output 1

5 8
4 9

Here, Takahashi chose A=5, B=8, C=4, D=9.
This choice generates 10 strings S_1,S_2,\dots,S_{10}, each of length 10, where the 4-th through 9-th characters of S_5,S_6,S_7,S_8 are #, and the other characters are ..
These are equal to the strings given in the input.

Sample Input 2

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

Sample Output 2

2 2
3 3

Sample Input 3

##########
##########
##########
##########
##########
##########
##########
##########
##########
##########

Sample Output 3

1 10
1 10

Problem Statement

You are given a sequence A=(A_0,A_1,\dots,A_{63}) of length 64 consisting of 0 and 1.

Find A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63}.

Constraints

• A_i is 0 or 1.

Sample Input 1

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

13

A_0 2^0 + A_1 2^1 + \dots + A_{63} 2^{63} = 2^0 + 2^2 + 2^3 = 13.

Sample Input 2

1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0

Sample Output 2

766067858140017173

Problem Statement

There is a directed graph with N vertices and N edges.
The i-th edge goes from vertex i to vertex A_i. (The constraints guarantee that i \neq A_i.)
Find a directed cycle without the same vertex appearing multiple times.
It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices B = (B_1, B_2, \dots, B_M) is called a directed cycle when all of the following conditions are satisfied:

• M \geq 2
• The edge from vertex B_i to vertex B_{i+1} exists. (1 \leq i \leq M-1)
• The edge from vertex B_M to vertex B_1 exists.
• If i \neq j, then B_i \neq B_j.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le N
• A_i \neq i

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges 1 \rightarrow 2 and 2 \rightarrow 1.
In this case, 1 \rightarrow 2 \rightarrow 1 is indeed a directed cycle.

Here is the graph corresponding to this input, where 1 \leftrightarrow 2 represents the existence of both 1 \rightarrow 2 and 2 \rightarrow 1:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

Problem Statement

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

• Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Sample Input 1

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

Sample Output 1

2

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.

Sample Input 2

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

Sample Output 2

3

Problem Statement

You are given a sequence of length N: A=(A_1,A_2,\ldots,A_N).
Find the number of triples (i,j,k) that satisfy both of the following conditions.

• 1\leq i \lt j \lt k \leq N
• A_i, A_j, and A_k are distinct.

Constraints

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

Sample Input 1

4
3 1 4 1

Sample Output 1

2

The two triples (i,j,k) satisfying the conditions are (1,2,3) and (1,3,4).

Sample Input 2

10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990

Sample Output 2

120

Sample Input 3

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

Sample Output 3

355

Problem Statement

We have N books numbered 1 to N.
Book i assumes that you have read C_i books, the j-th of which is book P_{i,j}: you must read all these C_i books before reading book i.
Here, you can read all the books in some order.

You are trying to read the minimum number of books required to read book 1.
Print the numbers of the books you must read excluding book 1 in the order they should be read. Under this condition, the set of books to read is uniquely determined.
If there are multiple reading orders that satisfy the condition, you may print any of them.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq C_i < N
• \sum_{i=1}^{N} C_i \leq 2 \times 10^5
• C_1 \geq 1
• 1 \leq P_{i,j} \leq N
• P_{i,j} \neq P_{i,k} for 1 \leq j < k \leq C_i.
• It is possible to read all the books.

Sample Input 1

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

Sample Output 1

5 3 4 2

To read book 1, you must read books 2,3,4; to read book 2, you must read books 3,5; to read book 4, you must read book 5. To read books 3,5,6, you do not have to read any other books.

For example, if you read books 5,3,4,2 in this order, you can read book 1. This is a correct answer, because you will never be able to read book 1 with three or fewer books read. As another example, reading books 3,5,4,2 in this order also allows you to read book 1 with 4 books read.

Sample Input 2

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

Sample Output 2

6 5 4 3 2

Sample Input 3

8
1 5
1 6
1 7
1 8
0
0
0
0

Sample Output 3

5

Problem Statement

There are N cards called card 1, card 2, \ldots, card N. On card i (1\leq i\leq N), an integer A_i is written.

For K=1, 2, \ldots, N, solve the following problem.

We have a bag that contains K cards: card 1, card 2, \ldots, card K.
Let us perform the following operation twice, and let x and y be the numbers recorded, in the recorded order.

Draw a card from the bag uniformly at random, and record the number written on that card. Then, return the card to the bag.

Print the expected value of \max(x,y), modulo 998244353 (see Notes).
Here, \max(x,y) denotes the value of the greater of x and y (or x if they are equal).

Notes

It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} with two coprime integers P and Q, it can be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print this R.

Constraints

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

Sample Input 1

3
5 7 5

Sample Output 1

5
499122183
443664163

For instance, the answer for K=2 is found as follows.

The bag contains card 1 and card 2, with A_1=5 and A_2=7 written on them, respectively.

• If you draw card 1 in the first draw and card 1 again in the second draw, we have x=y=5, so \max(x,y)=5.
• If you draw card 1 in the first draw and card 2 in the second draw, we have x=5 and y=7, so \max(x,y)=7.
• If you draw card 2 in the first draw and card 1 in the second draw, we have x=7 and y=5, so \max(x,y)=7.
• If you draw card 2 in the first draw and card 2 again in the second draw, we have x=y=7, so \max(x,y)=7.

These events happen with the same probability, so the sought expected value is \frac{5+7+7+7}{4}=\frac{13}{2}. We have 499122183\times 2\equiv 13 \pmod{998244353}, so 499122183 should be printed.

Sample Input 2

7
22 75 26 45 72 81 47

Sample Output 2

22
249561150
110916092
873463862
279508479
360477194
529680742