Problem Statement

Let us define a function f as f(x) = x^2 + 2x + 3.
Given an integer t, find f(f(f(t)+t)+f(f(t))).
Here, it is guaranteed that the answer is an integer not greater than 2 \times 10^9.

Constraints

• t is an integer between 0 and 10 (inclusive).

Sample Input 1

0

Sample Output 1

1371

The answer is computed as follows.

• f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
• f(t)+t = 3 + 0 = 3
• f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
• f(f(t)) = f(3) = 18
• f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371

Sample Input 2

3

Sample Output 2

722502

Sample Input 3

10

Sample Output 3

1111355571

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:

• remove the initial element of A and append a 0 to the tail of A.

Print all the elements of A after the operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 100
• 1 \leq A_i \leq 100
• All values in the input are integers.

Sample Input 1

3 2
2 7 8

Sample Output 1

8 0 0

Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.

Sample Input 2

3 4
9 9 9

Sample Output 2

0 0 0

Sample Input 3

9 5
1 2 3 4 5 6 7 8 9

Sample Output 3

6 7 8 9 0 0 0 0 0

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

You are given integer sequences, each of length N: A = (A_1, A_2, \dots, A_N) and B = (B_1, B_2, \dots, B_N).
All elements of A are different. All elements of B are different, too.

Print the following two values.

1. The number of integers contained in both A and B, appearing at the same position in the two sequences. In other words, the number of integers i such that A_i = B_i.
2. The number of integers contained in both A and B, appearing at different positions in the two sequences. In other words, the number of pairs of integers (i, j) such that A_i = B_j and i \neq j.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• A_1, A_2, \dots, A_N are all different.
• B_1, B_2, \dots, B_N are all different.
• All values in input are integers.

Sample Input 1

4
1 3 5 2
2 3 1 4

Sample Output 1

1
2

There is one integer contained in both A and B, appearing at the same position in the two sequences: A_2 = B_2 = 3.
There are two integers contained in both A and B, appearing at different positions in the two sequences: A_1 = B_3 = 1 and A_4 = B_1 = 2.

Sample Input 2

3
1 2 3
4 5 6

Sample Output 2

0
0

In both 1. and 2., no integer satisfies the condition.

Sample Input 3

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

Sample Output 3

3
2

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

We have N fuses connected in series. The i-th fuse from the left has a length of A_i centimeters and burns at a constant speed of B_i centimeters per second.

Consider igniting this object from left and right ends simultaneously. Find the distance between the position where the two flames will meet and the left end of the object.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i,B_i \leq 1000
• All values in input are integers.

Sample Input 1

3
1 1
2 1
3 1

Sample Output 1

3.000000000000000

The two flames will meet at 3 centimeters from the left end of the object.

Sample Input 2

3
1 3
2 2
3 1

Sample Output 2

3.833333333333333

Sample Input 3

5
3 9
1 2
4 6
1 5
5 3

Sample Output 3

8.916666666666668

Problem Statement

You are given an integer N. Find the number of pairs (i,j) of positive integers at most N that satisfy the following condition:

• i \times j is a square number.

Constraints

• 1 \le N \le 2 \times 10^5
• N is an integer.

Sample Input 1

4

Sample Output 1

6

The six pairs (1,1),(1,4),(2,2),(3,3),(4,1),(4,4) satisfy the condition.

On the other hand, (2,3) does not, since 2 \times 3 =6 is not a square number.

Sample Input 2

254

Sample Output 2

896

Problem Statement

We have an N \times N chessboard. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of this board.
The board is described by N strings S_i.
The j-th character of the string S_i, S_{i,j}, means the following.

• If S_{i,j}= ., the square (i, j) is empty.
• If S_{i,j}= #, the square (i, j) is occupied by a white pawn, which cannot be moved or removed.

We have put a white bishop on the square (A_x, A_y).
Find the minimum number of moves needed to move this bishop from (A_x, A_y) to (B_x, B_y) according to the rules of chess (see Notes).
If it cannot be moved to (B_x, B_y), report -1 instead.

Notes

A white bishop on the square (i, j) can go to the following positions in one move.

• For each positive integer d, it can go to (i+d,j+d) if all of the conditions are satisfied.

  • The square (i+d,j+d) exists in the board.
  • For every positive integer l \le d, (i+l,j+l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i+d,j-d) if all of the conditions are satisfied.

  • The square (i+d,j-d) exists in the board.
  • For every positive integer l \le d, (i+l,j-l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i-d,j+d) if all of the conditions are satisfied.

  • The square (i-d,j+d) exists in the board.
  • For every positive integer l \le d, (i-l,j+l) is not occupied by a white pawn.

• For each positive integer d, it can go to (i-d,j-d) if all of the conditions are satisfied.

  • The square (i-d,j-d) exists in the board.
  • For every positive integer l \le d, (i-l,j-l) is not occupied by a white pawn.

Constraints

• 2 \le N \le 1500
• 1 \le A_x,A_y \le N
• 1 \le B_x,B_y \le N
• (A_x,A_y) \neq (B_x,B_y)
• S_i is a string of length N consisting of . and #.
• S_{A_x,A_y}= .
• S_{B_x,B_y}= .

Sample Input 1

5
1 3
3 5
....#
...#.
.....
.#...
#....

Sample Output 1

3

We can move the bishop from (1,3) to (3,5) in three moves as follows, but not in two or fewer moves.

• (1,3) \rightarrow (2,2) \rightarrow (4,4) \rightarrow (3,5)

Sample Input 2

4
3 2
4 2
....
....
....
....

Sample Output 2

-1

There is no way to move the bishop from (3,2) to (4,2).

Sample Input 3

18
18 1
1 18
..................
.####.............
.#..#..####.......
.####..#..#..####.
.#..#..###...#....
.#..#..#..#..#....
.......####..#....
.............####.
..................
..................
.####.............
....#..#..#.......
.####..#..#..####.
.#.....####..#....
.####.....#..####.
..........#..#..#.
.............####.
..................

Sample Output 3

9

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. (A graph is said to be simple if it has no multi-edges and no self-loops.)
For i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.

A sequence (A_1, A_2, \ldots, A_k) is said to be a path of length k if both of the following two conditions are satisfied:

• For all i = 1, 2, \dots, k, it holds that 1 \leq A_i \leq N.
• For all i = 1, 2, \ldots, k-1, Vertex A_i and Vertex A_{i+1} are directly connected by an edge.

An empty sequence is regarded as a path of length 0.

Let S = s_1s_2\ldots s_N be a string of length N consisting of 0 and 1. A path A = (A_1, A_2, \ldots, A_k) is said to be a good path with respect to S if the following conditions are satisfied:

• For all i = 1, 2, \ldots, N, it holds that:
  • if s_i = 0, then A has even number of i's.
  • if s_i = 1, then A has odd number of i's.

There are 2^N possible S (in other words, there are 2^N strings of length N consisting of 0 and 1). Find the sum of "the length of the shortest good path with respect to S" over all those S.

Under the Constraints of this problem, it can be proved that, for any string S of length N consisting of 0 and 1, there is at least one good path with respect to S.

Constraints

• 2 \leq N \leq 17
• N-1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq u_i, v_i \leq N
• The given graph is simple and connected.
• All values in input are integers.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

14

• For S = 000, the empty sequence () is the shortest good path with respect to S, whose length is 0.
• For S = 100, (1) is the shortest good path with respect to S, whose length is 1.
• For S = 010, (2) is the shortest good path with respect to S, whose length is 1.
• For S = 110, (1, 2) is the shortest good path with respect to S, whose length is 2.
• For S = 001, (3) is the shortest good path with respect to S, whose length is 1.
• For S = 101, (1, 2, 3, 2) is the shortest good path with respect to S, whose length is 4.
• For S = 011, (2, 3) is the shortest good path with respect to S, whose length is 2.
• For S = 111, (1, 2, 3) is the shortest good path with respect to S, whose length is 3.

Therefore, the sought answer is 0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14.

Sample Input 2

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

Sample Output 2

108