Problem Statement

You are given a string S consisting of lowercase English letters.

Uppercase each character of S and print the resulting string T.

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

abc

Sample Output 1

ABC

Uppercase each character of abc, and you have ABC.

Sample Input 2

a

Sample Output 2

A

Sample Input 3

abcdefghjiklnmoqprstvuwxyz

Sample Output 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ

Problem Statement

Takahashi had his N-th birthday, when he was T centimeters tall.
Additionally, we know the following facts:

• In each year between Takahashi's birth (0-th birthday) and his X-th birthday, his height increased by D centimeters. More formally, for each i = 1, 2, \ldots, X, his height increased by D centimeters between his (i-1)-th birthday and his i-th birthday.
• Between Takahashi's X-th birthday and his N-th birthday, his height did not change.

Find Takahashi's height on his M-th birthday, in centimeters.

Constraints

• 0 \leq M \lt N \leq 100
• 1 \leq X \leq N
• 1 \leq T \leq 200
• 1 \leq D \leq 100
• Takahashi was at least 1 centimeter tall at his birth.
• All values in input are integers.

Sample Input 1

38 20 17 168 3

Sample Output 1

168

In this sample, Takahashi was 168 centimeters tall on his 38-th birthday. Also, his height did not change between his 17-th birthday and 38-th birthday.
From these facts, we find that he was 168 centimeters tall on his 20-th birthday, so the answer is 168.

Sample Input 2

1 0 1 3 2

Sample Output 2

1

In this sample, Takahashi was 1 centimeter tall on his 0(=M)-th birthday and 3(=T) centimeters tall on his 1(=N)-st birthday.

Sample Input 3

100 10 100 180 1

Sample Output 3

90

Problem Statement

You are given N integers A_1,A_2,\dots,A_N, one per line, over N lines. However, N is not given in the input.
Furthermore, the following is guaranteed:

• A_i \neq 0 ( 1 \le i \le N-1 )
• A_N = 0

Print A_N, A_{N-1},\dots,A_1 in this order.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le A_i \le 10^9 ( 1 \le i \le N-1 )
• A_N = 0

Sample Input 1

3
2
1
0

Sample Output 1

0
1
2
3

Note again that N is not given in the input. Here, N=4 and A=(3,2,1,0).

Sample Input 2

0

Sample Output 2

0

A=(0).

Sample Input 3

123
456
789
987
654
321
0

Sample Output 3

0
321
654
987
789
456
123

Problem Statement

You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)

S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.

If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.

Constraints

• 1 \leq N \leq M \leq 100
• S is a string of length N consisting of lowercase English letters.
• T is a string of length M consisting of lowercase English letters.

Sample Input 1

3 7
abc
abcdefg

Sample Output 1

1

S is a prefix of T but not a suffix, so you should print 1.

Sample Input 2

3 4
abc
aabc

Sample Output 2

2

S is a suffix of T but not a prefix.

Sample Input 3

3 3
abc
xyz

Sample Output 3

3

S is neither a prefix nor a suffix of T.

Sample Input 4

3 3
aaa
aaa

Sample Output 4

0

S and T may coincide, in which case S is both a prefix and a suffix of T.

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for N days as a string S of length N consisting of 0, 1, and 2.
Specifically, for an integer i satisfying 1\leq i\leq N,

• if the i-th character of S is 0, he has no plan scheduled for the i-th day;
• if the i-th character of S is 1, he plans to go out for a meal on the i-th day;
• if the i-th character of S is 2, he plans to attend a competitive programming event on the i-th day.

Takahashi has M plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

• On days he goes out for a meal, he will wear a plain or logo T-shirt.
• On days he attends a competitive programming event, he will wear a logo T-shirt.
• On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
• Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the N days. If he does not need to buy new T-shirts, print 0.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

• 1\leq M\leq N\leq 1000
• S is a string of length N consisting of 0, 1, and 2.
• N and M are integers.

Sample Input 1

6 1
112022

Sample Output 1

2

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

• On the first day, he wears a logo T-shirt to go out for a meal.
• On the second day, he wears a plain T-shirt to go out for a meal.
• On the third day, he wears a logo T-shirt to attend a competitive programming event.
• On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
• On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
• On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print 2.

Sample Input 2

3 1
222

Sample Output 2

3

Sample Input 3

2 1
01

Sample Output 3

0

He does not need to buy new T-shirts.

Problem Statement

In AtCoder Land, there are N popcorn stands numbered 1 to N. They have M different flavors of popcorn, labeled 1, 2, \dots, M, but not every stand sells all flavors of popcorn.

Takahashi has obtained information about which flavors of popcorn are sold at each stand. This information is represented by N strings S_1, S_2, \dots, S_N of length M. If the j-th character of S_i is o, it means that stand i sells flavor j of popcorn. If it is x, it means that stand i does not sell flavor j. Each stand sells at least one flavor of popcorn, and each flavor of popcorn is sold at least at one stand.

Takahashi wants to try all the flavors of popcorn but does not want to move around too much. Determine the minimum number of stands Takahashi needs to visit to buy all the flavors of popcorn.

Constraints

• N and M are integers.
• 1 \leq N, M \leq 10
• Each S_i is a string of length M consisting of o and x.
• For every i (1 \leq i \leq N), there is at least one o in S_i.
• For every j (1 \leq j \leq M), there is at least one i such that the j-th character of S_i is o.

Sample Input 1

3 5
oooxx
xooox
xxooo

Sample Output 1

2

By visiting the 1st and 3rd stands, you can buy all the flavors of popcorn. It is impossible to buy all the flavors from a single stand, so the answer is 2.

Sample Input 2

3 2
oo
ox
xo

Sample Output 2

1

Sample Input 3

8 6
xxoxxo
xxoxxx
xoxxxx
xxxoxx
xxoooo
xxxxox
xoxxox
oxoxxo

Sample Output 3

3

Problem Statement

You are given a simple undirected graph G with N vertices and M edges (a simple graph does not contain self-loops or multi-edges). For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i.

Print the number of pairs of integers (u, v) that satisfy 1 \leq u \lt v \leq N and both of the following conditions.

• The graph G does not have an edge connecting vertex u and vertex v.
• Adding an edge connecting vertex u and vertex v in the graph G results in a bipartite graph.

Constraints

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

Sample Input 1

5 4
4 2
3 1
5 2
3 2

Sample Output 1

2

We have two pairs of integers (u, v) that satisfy the conditions in the problem statement: (1, 4) and (1, 5). Thus, you should print 2.
The other pairs do not satisfy the conditions. For instance, for (1, 3), the graph G has an edge connecting vertex 1 and vertex 3; for (4, 5), adding an edge connecting vertex 4 and vertex 5 in the graph G does not result in a bipartite graph.

Sample Input 2

4 3
3 1
3 2
1 2

Sample Output 2

0

Note that the given graph may not be bipartite or connected.

Sample Input 3

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

Sample Output 3

9

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the cell at the i-th row (1\leq i\leq H) from the top and j-th column (1\leq j\leq W) from the left.

Initially, there is a slime with strength S _ {i,j} in cell (i,j), and Takahashi is the slime in the cell (P,Q).

Find the maximum possible strength of Takahashi after performing the following action any number of times (possibly zero):

• Among the slimes adjacent to him, choose one whose strength is strictly less than \dfrac{1}{X} times his strength and absorb it. As a result, the absorbed slime disappears, and Takahashi's strength increases by the strength of the absorbed slime.

When performing the above action, the gap left by the disappeared slime is immediately filled by Takahashi, and the slimes that were adjacent to the disappeared one (if any) become newly adjacent to Takahashi (refer to the explanation in sample 1).

Constraints

• 1\leq H,W\leq500
• 1\leq P\leq H
• 1\leq Q\leq W
• 1\leq X\leq10^9
• 1\leq S _ {i,j}\leq10^{12}
• All input values are integers.

Sample Input 1

3 3 2
2 2
14 6 9
4 9 20
17 15 7

Sample Output 1

28

Initially, the strength of the slime in each cell is as follows:

For example, Takahashi can act as follows:

• Absorb the slime in cell (2,1). His strength becomes 9+4=13, and the slimes in cells (1,1) and (3,1) become newly adjacent to him.
• Absorb the slime in cell (1,2). His strength becomes 13+6=19, and the slime in cell (1,3) becomes newly adjacent to him.
• Absorb the slime in cell (1,3). His strength becomes 19+9=28.

After these actions, his strength is 28.

No matter how he acts, it is impossible to get a strength greater than 28, so print 28.

Note that Takahashi can only absorb slimes whose strength is strictly less than half of his strength. For example, in the figure on the right above, he cannot absorb the slime in cell (1,1).

Sample Input 2

3 4 1
1 1
5 10 1 1
10 1 1 1
1 1 1 1

Sample Output 2

5

He cannot absorb any slimes.

Sample Input 3

8 10 2
1 5
388 130 971 202 487 924 247 286 237 316
117 166 918 106 336 928 493 391 235 398
124 280 425 955 212 988 227 222 307 226
336 302 478 246 950 368 291 236 170 101
370 200 204 141 287 410 388 314 205 460
291 104 348 337 404 399 416 263 415 339
105 420 302 334 231 481 466 366 401 452
119 432 292 403 371 417 351 231 482 184

Sample Output 3

1343

Problem Statement

There are N sequences of length M, denoted as A_1, A_2, \ldots, A_N. The i-th sequence is represented by M integers A_{i,1}, A_{i,2}, \ldots, A_{i,M}.

Two sequences X and Y of length M are said to be similar if and only if the number of indices i (1 \leq i \leq M) such that X_i = Y_i is odd.

Find the number of pairs of integers (i,j) satisfying 1 \leq i < j \leq N such that A_i and A_j are similar.

Constraints

• 1 \leq N \leq 2000
• 1 \leq M \leq 2000
• 1 \leq A_{i,j} \leq 999
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 3 4
2 3 4

Sample Output 1

1

The pair (i,j) = (1,2) satisfies the condition because there is only one index k such that A_{1,k} = A_{2,k}, which is k=1.

The pairs (i,j) = (1,3), (2,3) do not satisfy the condition, making (1,2) the only pair that does.

Sample Input 2

6 5
8 27 27 10 24
27 8 2 4 5
15 27 26 17 24
27 27 27 27 27
27 7 22 11 27
19 27 27 27 27

Sample Output 2

5