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

Keyence has a culture of addressing everyone with the honorific "san," regardless of their role, age, or position. Even a new employee would call the president "Nakata-san." [Translator's note: this is a bit unusual in Japan.]

You are given a person's surname and first name as strings S and T, respectively.

Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.

Constraints

• Each of S and T is a string that satisfies the following conditions.
  • The length is between 1 and 10, inclusive.
  • The first character is an uppercase English letter.
  • All characters except the first one are lowercase English letters.

Sample Input 1

Takahashi Chokudai

Sample Output 1

Takahashi san

Print the concatenation of the surname (Takahashi), a space ( ), and the honorific (san) in this order.

Sample Input 2

K Eyence

Sample Output 2

K san

Problem Statement

You are given an integer N and a sequence S=(S_1,\ldots,S_N) of length N.

Find a sequence A=(A_1,\ldots,A_N) of length N that satisfies the following condition for all k=1,\ldots,N:

• A_1+A_2+\ldots+A_k = S_k.

Such a sequence A always exists and is unique.

Constraints

• 1 \leq N \leq 10
• -10^9\leq S_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
3 4 8

Sample Output 1

3 1 4

The sequence in the output actually satisfies all the conditions:

• A_1=3=S_1;
• A_1+A_2=3+1=4=S_2;
• A_1+A_2+A_3=3+1+4=8=S_3.

Sample Input 2

10
314159265 358979323 846264338 -327950288 419716939 -937510582 97494459 230781640 628620899 -862803482

Sample Output 2

314159265 44820058 487285015 -1174214626 747667227 -1357227521 1035005041 133287181 397839259 -1491424381

Problem Statement

In the calendar of AtCoderLand, a year consists of M months: month 1, month 2, \dots, month M. The i-th month consists of D_i days: day 1, day 2, \dots, day D_i.
Furthermore, the number of days in a year is odd, that is, D_1+D_2+\dots+D_M is odd.
Find what day of what month is the middle day of the year.
In other words, let day 1 of month 1 be the first day, and find a and b such that the ((D_1+D_2+\dots+D_M+1)/2)-th day is day b of month a.

Constraints

• All input values are integers.
• 1 \le M \le 100
• 1 \le D_i \le 100
• D_1 + D_2 + \dots + D_M is odd.

Sample Input 1

12
31 28 31 30 31 30 31 31 30 31 30 31

Sample Output 1

7 2

In this input, a year consists of 31+28+31+30+31+30+31+31+30+31+30+31=365 days.
Let us find the middle day, which is the ((365+1)/2 = 183)-th day.

• Months 1,2,3,4,5,6 contain a total of 181 days.
• Day 1 of month 7 is the 182-th day.
• Day 2 of month 7 is the 183-th day.

Thus, the answer is day 2 of month 7.

Sample Input 2

1
1

Sample Output 2

1 1

Sample Input 3

6
3 1 4 1 5 9

Sample Output 3

5 3

Problem Statement

There is a 10^9-story building with N ladders.
Takahashi, who is on the 1-st (lowest) floor, wants to reach the highest floor possible by using ladders (possibly none).
The ladders are numbered from 1 to N, and ladder i connects the A_i-th and B_i-th floors. One can use ladder i in either direction to move from the A_i-th floor to the B_i-th floor or vice versa, but not between other floors.
Takahashi can freely move within the same floor, but cannot move between floors without using ladders.
What is the highest floor Takahashi can reach?

Constraints

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

Sample Input 1

4
1 4
4 3
4 10
8 3

Sample Output 1

10

He can reach the 10-th floor by using ladder 1 to get to the 4-th floor and then ladder 3 to get to the 10-th floor.

Sample Input 2

6
1 3
1 5
1 12
3 5
3 12
5 12

Sample Output 2

12

Sample Input 3

3
500000000 600000000
600000000 700000000
700000000 800000000

Sample Output 3

1

He may be unable to move between floors.

Problem Statement

We have two figures S and T on a two-dimensional grid with square cells.

S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.

Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.

Constraints

• 1 \leq N \leq 200
• Each of S and T consists of # and ..
• Each of S and T contains at least one #.

Sample Input 1

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

Sample Output 1

Yes

We can match S to T by rotating it 90-degrees counter-clockwise and translating it.

Sample Input 2

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

Sample Output 2

No

It is impossible to match them by 90-degree rotations and translations.

Sample Input 3

4
#...
..#.
..#.
....
#...
#...
..#.
....

Sample Output 3

Yes

Each of S and T may not be connected.

Sample Input 4

4
#...
.##.
..#.
....
##..
#...
..#.
....

Sample Output 4

No

Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.

Problem Statement

You are given an integer sequence of length N: A=(A_1,A_2,\ldots,A_N).

You will perform the following consecutive operations just once:

• Choose an integer x (0\leq x \leq N). If x is 0, do nothing. If x is 1 or greater, replace each of A_1,A_2,\ldots,A_x with L.

• Choose an integer y (0\leq y \leq N). If y is 0, do nothing. If y is 1 or greater, replace each of A_{N},A_{N-1},\ldots,A_{N-y+1} with R.

Print the minimum possible sum of the elements of A after the operations.

Constraints

• 1 \leq N \leq 2\times 10^5
• -10^9 \leq L, R\leq 10^9
• -10^9 \leq A_i\leq 10^9
• All values in input are integers.

Sample Input 1

5 4 3
5 5 0 6 3

Sample Output 1

14

If you choose x=2 and y=2, you will get A = (4,4,0,3,3), for the sum of 14, which is the minimum sum achievable.

Sample Input 2

4 10 10
1 2 3 4

Sample Output 2

10

If you choose x=0 and y=0, you will get A = (1,2,3,4), for the sum of 10, which is the minimum sum achievable.

Sample Input 3

10 -5 -3
9 -6 10 -1 2 10 -1 7 -15 5

Sample Output 3

-58

L, R, and A_i may be negative.

Problem Statement

A country has N cities and M power plants, which we collectively call places.
The places are numbered 1,2,\dots,N+M, among which Places 1,2,\dots,N are the cities and Places N+1,N+2,\dots,N+M are the power plants.

This country has E power lines. Power Line i (1 \le i \le E) connects Place U_i and Place V_i bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.

Now, Q events will happen. In the i-th (1 \le i \le Q) event, Power Line X_i breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.

Find the number of electrified cities right after each events.

Constraints

• All values in input are integers.
• 1 \le N,M
• N+M \le 2 \times 10^5
• 1 \le Q \le E \le 5 \times 10^5
• 1 \le U_i < V_i \le N+M
• If i \neq j, then U_i \neq U_j or V_i \neq V_j.
• 1 \le X_i \le E
• X_i are distinct.

Sample Input 1

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

Sample Output 1

4
4
2
2
2
1

Initially, all cities are electrified.

• The 1-st event breaks Power Line 3 that connects Point 5 and Point 10.
  • Now City 5 is no longer electrified, while 4 cities remain electrified.
• The 2-nd event breaks Power Line 5 that connects Point 2 and Point 9.
• The 3-rd event breaks Power Line 8 that connects Point 3 and Point 6.
  • Now Cities 2 and 3 are no longer electrified, while 2 cities remain electrified.
• The 4-th event breaks Power Line 10 that connects Point 1 and Point 8.
• The 5-th event breaks Power Line 2 that connects Point 4 and Point 10.
• The 6-th event breaks Power Line 7 that connects Point 1 and Point 7.
  • Now City 1 is no longer electrified, while 1 city remains electrified.

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. (i, j) contains an integer A_{i,j}.

Takahashi will depart (1, 1) and repeatedly move one square right or down until reaching (H, W). It is not allowed to exit the grid.

The cost of this travel is defined as:

the sum of the K greatest integers among the integers written on the H+W-1 squares traversed.

Find the minimum possible cost.

Constraints

• 1 \leq H,W \leq 30
• 1 \leq K < H+W
• 1 \leq A_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

1 3 2
3 4 5

Sample Output 1

9

There is only one way to travel, where the traversed squares contain the integers 5, 4, 3 from largest to smallest, so we print 9(=5+4).

Sample Input 2

2 2 1
3 2
4 3

Sample Output 2

3

The minimum cost is achieved by traversing (1,1), (1,2), (2,2) in this order.

Sample Input 3

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

Sample Output 3

21