Problem Statement

You are given integers A and B between 0 and 255 (inclusive). Find a non-negative integer C such that A \text{ xor }C=B.

It can be proved that there uniquely exists such C, and it will be between 0 and 255 (inclusive).

Constraints

• 0\leq A,B \leq 255
• All values in input are integers.

Sample Input 1

3 6

Sample Output 1

5

When written in binary, 3 will be 11, and 5 will be 101. Thus, their \text{xor} will be 110 in binary, or 6 in decimal.

In short, 3 \text{ xor } 5 = 6, so the answer is 5.

Sample Input 2

10 12

Sample Output 2

6

Problem Statement

N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.

The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.

Constraints

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

Sample Input 1

6
1 123 12345 12 1234 123456

Sample Output 1

3

It is Player 3 who ranks fifth among the six players.

Sample Input 2

5
3 1 4 15 9

Sample Output 2

5

Problem Statement

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

• If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
• If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

• 1 \leq H,W \leq 10^9
• 1 \leq N \leq \min(10^5,HW)
• 1 \leq A_i \leq H
• 1 \leq B_i \leq W
• All pairs (A_i,B_i) are distinct.
• All values in input are integers.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

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

Problem Statement

The Republic of AtCoder has N cities numbered 1 through N and N-1 roads numbered 1 through N-1. Road i connects City A_i and City B_i bidirectionally. It is guaranteed that one can travel between every pair of cities using roads.

Takahashi will depart City 1 and have a journey by repeating the following.

• If there are unvisited cities that are directly connected to the city Takahashi is in now, he goes to the city with the smallest number among those cities.
• Otherwise,
  • if he is in City 1, he ends the journey;
  • otherwise, he goes to the city he was in just before visiting the current city for the first time.

Find the sequence of cities visited by Takahashi in the order he visits them.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1\leq A_i,B_i \leq N
• It is possible to travel between every pair of cities using roads.

Sample Input 1

4
1 2
4 2
3 1

Sample Output 1

1 2 4 2 1 3 1

His journey will be as follows.

• Start in City 1.
• The unvisited cities directly connected to City 1 are City 2 and 3. Go to the city with the smaller number, that is, City 2.
• The unvisited city directly connected to City 2 is City 4. Go there.
• There is no unvisited city directly connected to City 4. Go back to City 2.
• There is no unvisited city directly connected to City 2. Go to City 1, where he was in just before visiting City 2 for the first time.
• The unvisited city directly connected to City 1 is City 3. Go there.
• There is no unvisited city directly connected to City 3. Go back to City 1.
• There is no unvisited city directly connected to City 1. End the journey.

Sample Input 2

5
1 2
1 3
1 4
1 5

Sample Output 2

1 2 1 3 1 4 1 5 1

Problem Statement

There is a town divided into a grid of cells with H rows and W columns. The cell at the i-th row from the top and j-th column from the left is a passable space if S_{i,j} is . and a block if S_{i,j} is #.

Takahashi will go from his house to a fish market. His house is in the cell at the top-left corner, and the fish market is in the cell at the bottom-right corner.

Takahashi can move one cell up, down, left, or right to a passable cell. He cannot leave the town. He cannot enter a block, either. However, his physical strength allows him to destroy all blocks in a square region with 2\times 2 cells of his choice with one punch, making these cells passable.

Find the minimum number of punches needed for Takahashi to reach the fish market.

Constraints

• 2 \leq H,W \leq 500
• H and W are integers.
• S_{i,j} is . or #.
• S_{1,1} and S_{H,W} are ..

Sample Input 1

5 5
..#..
#.#.#
##.##
#.#.#
..#..

Sample Output 1

1

He can reach the fish market by, for example, destroying the blocks in the square region with 2\times 2 cells marked * below.

..#..
#.**#
##**#
#.#.#
..#..

It is not required that all of the 2\times 2 cells in the region to punch are blocks.

Sample Input 2

5 7
.......
######.
.......
.######
.......

Sample Output 2

0

He can reach the fish market without destroying blocks, though he has to go a long way around.

Sample Input 3

8 8
.#######
########
########
########
########
########
########
#######.

Sample Output 3

5

Problem Statement

Let the similarity f(X,Y) between two strings X and Y be the length of their longest common prefix.
For example, the similarity between abc and axbc is 1, and the similarity between aaa and aaaa is 3.

You are given a string S of length N. Let S_i be the suffix of S beginning with the i-th character of S. For each k=1,\ldots,N, find f(S_k,S_1)+f(S_k,S_2)+\ldots+f(S_k,S_N).

Constraints

• 1 \leq N \leq 10^6
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

3
abb

Sample Output 1

3
3
2

S_1 is abb, S_2 is bb, and S_3 is b.

• For k=1: f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3.
• For k=2: f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3.
• For k=3: f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2.

Sample Input 2

11
mississippi

Sample Output 2

11
16
14
12
13
11
9
7
4
3
4

Problem Statement

Given is a simple undirected graph G with N vertices and M edges. The vertices are numbered 1,2,\dots,N, the edges are numbered 1,2,\dots,M, and Edge i connects Vertex a_i and Vertex b_i.
Consider removing zero or more edges from G to get a new graph H. There are 2^M graphs that we can get as H. Among them, find the number of such graphs that Vertex 1 and Vertex k are directly or indirectly connected, for each integer k such that 2 \leq k \leq N.
Since the counts may be enormous, print them modulo 998244353.

Constraints

• 2 \leq N \leq 17
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq a_i \lt b_i \leq N
• (a_i, b_i) \neq (a_j, b_j) if i \neq j.
• All values in input are integers.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

2
1

We can get the following graphs as H.

• The graph with no edges. Vertex 1 is disconnected from any other vertex.
• The graph with only the edge connecting Vertex 1 and 2. Vertex 2 is reachable from Vertex 1.
• The graph with only the edge connecting Vertex 2 and 3. Vertex 1 is disconnected from any other vertex.
• The graph with both edges. Vertex 2 and 3 are reachable from Vertex 1.

Sample Input 2

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

Sample Output 2

43
31
37
41

Sample Input 3

2 0

Sample Output 3

0

Problem Statement

Takahashi has decided to wander around his house.
During his walk, he will roam between N points called Point 1, Point 2, \dots, Point N, where Point 1 is his house.
There are M pairs of points connected by roads; let (a_i, b_i) be the i-th of these pairs. There are p_{i, d} roads with a length of d (1 \leq d \leq T) kilometers connecting Point a_i and Point b_i.

Takahashi wants to know the number of T kilometers courses that begin and end at his house. Here, a T kilometers course is defined as follows.

• An alternating sequence with points and roads v_0 = 1, e_0, v_1, \dots,e_{k-1}, v_k = 1 such that e_i (0 \leq i \leq k-1) connects v_i and v_{i+1}, and the total length of e_i is T kilometers.

Help Takahashi by finding the number of such courses modulo 998244353. Two courses are considered different when they are different as sequences.

Constraints

• 2 \leq N \leq 10
• 1 \leq M \leq \min \left(10, \frac{N(N-1)}{2} \right)
• 1 \leq T \leq 4 \times 10^4
• 1 \leq a_i \lt b_i \leq N
• (a_i, b_i) \neq (a_j, b_j) if i \neq j.
• 0 \leq p_{i,j} \lt 998244353

Sample Input 1

3 2 2
1 2
1 0
1 3
2 0

Sample Output 1

5

Around his house, there are:

• one 1-kilometer road connecting Point 1 and Point 2, and
• two 1-kilometer roads connecting Point 1 and Point 3.

We have the following five desirable courses:

• 1 \times 1 = 1 course that goes Point 1 \to Point 2 \to Point 1, and
• 2 \times 2 = 4 courses that goes Point 1 \to Point 3 \to Point 1.

Sample Input 2

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

Sample Output 2

130

Around his house, there are:

• three 1-kilometer roads connecting Point 1 and Point 2,
• one 2-kilometer road connecting Point 1 and Point 3, and
• two 1-kilometer roads connecting Point 2 and Point 3.

The desirable courses can be classified into the following categories, according to the points visited:

• Point 1 \to Point 2 \to Point 1 \to Point 2 \to Point 1,
• Point 1 \to Point 2 \to Point 3 \to Point 1,
• Point 1 \to Point 2 \to Point 3 \to Point 2 \to Point 1,
• Point 1 \to Point 3 \to Point 1, and
• Point 1 \to Point 3 \to Point 2 \to Point 1.

We have 81, 6, 36, 1, and 6 course(s) of these categories, respectively.

Sample Input 3

2 1 5
1 2
31415 92653 58979 32384 62643

Sample Output 3

844557977