Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.

• 1 \leq a \lt b \leq H
• 1 \leq c \lt d \leq W
• There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

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

Sample Input 1

5 6
......
..#.#.
..###.
..###.
......

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).

Sample Input 3

6 6
..####
..##.#
..####
..####
..####
......

Sample Output 3

2 5

Problem Statement

Takahashi runs an SNS "Twidai," which has N users from user 1 through user N. In Twidai, users can follow or unfollow other users.

Q operations have been performed since Twidai was launched. The i-th (1\leq i\leq Q) operation is represented by three integers T_i, A_i, and B_i, whose meanings are as follows:

• If T_i = 1: it means that user A_i follows user B_i. If user A_i is already following user B_i at the time of this operation, it does not make any change.
• If T_i = 2: it means that user A_i unfollows user B_i. If user A_i is not following user B_i at the time of this operation, it does not make any change.
• If T_i = 3: it means that you are asked to determine if users A_i and B_i are following each other. You need to print Yes if user A_i is following user B_i and user B_i is following user A_i, and No otherwise.

When the service was launched, no users were following any users.

Print the correct answers for all operations such that T_i = 3 in ascending order of i.

Constraints

• 2 \leq N \leq 10 ^ 9
• 1 \leq Q \leq 2\times10 ^ 5
• T _ i=1,2,3\ (1\leq i\leq Q)
• 1 \leq A _ i \leq N\ (1\leq i\leq Q)
• 1 \leq B _ i \leq N\ (1\leq i\leq Q)
• A _ i\neq B _ i\ (1\leq i\leq Q)
• There exists i\ (1\leq i\leq Q) such that T _ i=3.
• All values in the input are integers.

Sample Input 1

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

Sample Output 1

No
Yes
No
No

Twidai has three users. The nine operations are as follows.

• User 1 follows user 2. No other users are following or followed by any users.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, but user 2 is not following user 1, so No is the correct answer to this operation.
• User 2 follows user 1.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, and user 2 is following user 1, so Yes is the correct answer to this operation.
• User 2 follows user 3.
• User 3 follows user 2.
• Determine if users 1 and 3 are following each other. User 1 is not following user 3, and user 3 is not following user 1, so No is the correct answer to this operation.
• User 1 unfollows user 2.
• Determine if users 1 and 2 are following each other. User 2 is following user 1, but user 1 is not following user 2, so No is the correct answer to this operation.

Sample Input 2

2 8
1 1 2
1 2 1
3 1 2
1 1 2
1 1 2
1 1 2
2 1 2
3 1 2

Sample Output 2

Yes
No

A user may follow the same user multiple times.

Sample Input 3

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

Sample Output 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes

Problem Statement

Takahashi will encounter N monsters in order. The i-th monster (1\leq i\leq N) has a strength of A_i.

For each monster, he can choose to either let it go or defeat it.
Each action awards him experience points as follows:

• If he lets a monster go, he gains 0 experience points.
• If he defeats a monster with strength X, he gains X experience points.
  If it is an even-numbered defeated monster (2nd, 4th, ...), he gains an additional X experience points.

Find the maximum total experience points he can gain from the N monsters.

Constraints

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

Sample Input 1

5
1 5 3 2 7

Sample Output 1

28

If Takahashi defeats the 1st, 2nd, 3rd, and 5th monsters, and lets the 4th monster go, he gains experience points as follows:

• Defeats a monster with strength A_1=1. He gains 1 experience point.
• Defeats a monster with strength A_2=5. He gains 5 experience points. As it is the 2nd defeated monster, he gains an additional 5 points.
• Defeats a monster with strength A_3=3. He gains 3 experience points.
• Lets the 4th monster go. Takahashi gains no experience points.
• Defeats a monster with strength A_5=7. He gains 7 experience points. As it is the 4th defeated monster, he gains an additional 7 points.

Therefore, in this case, he gains 1+(5+5)+3+0+(7+7)=28 experience points.
Note that even if he encounters a monster, if he lets it go, it does not count as defeated.

He can gain at most 28 experience points no matter how he acts, so print 28.
As a side note, if he defeats all monsters in this case, he would gain 1+(5+5)+3+(2+2)+7=25 experience points.

Sample Input 2

2
1000000000 1000000000

Sample Output 2

3000000000

Beware that the answer may not fit in a 32-bit integer.

Problem Statement

You are given a sequence A of non-negative integers of length N, and an integer K. It is guaranteed that the binomial coefficient \dbinom{N}{K} is at most 10^6.

When choosing K distinct elements from A, find the maximum possible value of the XOR of the K chosen elements.

That is, find \underset{1\leq i_1\lt i_2\lt \ldots\lt i_K\leq N}{\max} A_{i_1}\oplus A_{i_2}\oplus \ldots \oplus A_{i_K}.

Constraints

• 1\leq K\leq N\leq 2\times 10^5
• 0\leq A_i<2^{60}
• \dbinom{N}{K}\leq 10^6
• All input values are integers.

Sample Input 1

4 2
3 2 6 4

Sample Output 1

7

Here are six ways to choose two distinct elements from (3,2,6,4).

• (3,2): The XOR is 3\oplus 2 = 1.
• (3,6): The XOR is 3\oplus 6 = 5.
• (3,4): The XOR is 3\oplus 4 = 7.
• (2,6): The XOR is 2\oplus 6 = 4.
• (2,4): The XOR is 2\oplus 4 = 6.
• (6,4): The XOR is 6\oplus 4 = 2.

Hence, the maximum possible value is 7.

Sample Input 2

10 4
1516 1184 1361 2014 1013 1361 1624 1127 1117 1759

Sample Output 2

2024

Problem Statement

There are N towns numbered Town 1, Town 2, \ldots, Town N.
There are also M Teleporters, each of which connects two towns bidirectionally so that a person can travel from one to the other in one minute.

The i-th Teleporter connects Town U_i and Town V_i bidirectionally. However, for some of the Teleporters, one of the towns it connects is undetermined; U_i=0 means that one of the towns the i-th Teleporter connects is Town V_i, but the other end is undetermined.

For i=1,2,\ldots,N, answer the following question.

When the Teleporters with undetermined ends are all determined to be connected to Town i, how many minutes is required at minimum to travel from Town 1 to Town N? If it is impossible to travel from Towns 1 to N using Teleporters only, print -1 instead.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1\leq M\leq 3\times 10^5
• 0\leq U_i<V_i\leq N
• If i \neq j, then (U_i,V_i)\neq (U_j,V_j).
• All values in input are integers.

Sample Input 1

3 2
0 2
1 2

Sample Output 1

-1 -1 2

When the Teleporters with an undetermined end are all determined to be connected to Town 1,
the 1-st and the 2-nd Teleporters both connect Towns 1 and 2. Then, it is impossible to travel from Town 1 to Town 3.

When the Teleporters with an undetermined end are all determined to be connected to Town 2,
the 1-st Teleporter connects Town 2 and itself, and the 2-nd one connects Towns 1 and 2. Again, it is impossible to travel from Town 1 to Town 3.

When the Teleporters with an undetermined end are all determined to be connected to Town 3,
the 1-st Teleporter connects Town 3 and Town 2, and the 2-nd one connects Towns 1 and 2. In this case, we can travel from Town 1 to Town 3 in two minutes.

• Use the 2-nd Teleporter to travel from Town 1 to Town 2.
• Use the 1-st Teleporter to travel from Town 2 to Town 3.

Therefore, -1,-1, and 2 should be printed in this order.

Note that, depending on which town the Teleporters with an undetermined end are connected to, there may be a Teleporter that connects a town and itself, or multiple Teleporters that connect the same pair of towns.

Sample Input 2

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

Sample Output 2

3 3 3 3 2