Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

• First, he painted the part from X=L_1 to X=R_1 red.
• Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

• 0\leq L_1<R_1\leq 100
• 0\leq L_2<R_2\leq 100
• All values in input are integers.

Sample Input 1

0 3 1 5

Sample Output 1

2

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

0

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

0

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

Problem Statement

You are given a positive integer N and two strings S and T, each of length N and consisting of lowercase English letters.

Find the Hamming distance between S and T. That is, find the number of integers i such that 1 \leq i \leq N and the i-th character of S is different from the i-th character of T.

Constraints

• 1\leq N \leq 100
• N is an integer.
• Each of S and T is a string of length N consisting of lowercase English letters.

Sample Input 1

6
abcarc
agcahc

Sample Output 1

2

S and T differ in the 2nd and 5th characters, but not in other characters. Thus, the answer is 2.

Sample Input 2

7
atcoder
contest

Sample Output 2

7

Sample Input 3

8
chokudai
chokudai

Sample Output 3

0

Sample Input 4

10
vexknuampx
vzxikuamlx

Sample Output 4

4

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

Takahashi wants to manage the waiting line in front of the AtCoder Restaurant. Initially, the waiting line is empty. Each person who joins the line holds a meal ticket with the menu number of the dish they will order.

Process Q queries in order. There are two types of queries, given in the following formats:

• 1 X: One person joins the end of the waiting line holding a ticket with menu number X.
• 2: Takahashi guides the person at the front of the waiting line into the restaurant. Print the menu number on that person’s ticket.

Constraints

• 1 \leq Q \leq 100
• 1 \leq X \leq 100
• For each query of the second type, there is at least one person in the line before guiding.
• All input values are integers.

Sample Input 1

6
1 3
1 1
1 15
2
1 3
2

Sample Output 1

3
1

Initially, the waiting line is empty.

• For the first query, a person holding a ticket with menu number 3 joins the end of the line. The sequence of menu numbers held by people in line from front to back is 3.
• For the second query, a person holding a ticket with menu number 1 joins the end of the line. The sequence becomes 3,1.
• For the third query, a person holding a ticket with menu number 15 joins the end of the line. The sequence becomes 3,1,15.
• For the fourth query, guide the person at the front into the restaurant. That person holds menu number 3, so print 3. The sequence becomes 1,15.
• For the fifth query, a person holding a ticket with menu number 3 joins the end of the line. The sequence becomes 1,15,3.
• For the sixth query, guide the person at the front into the restaurant. That person holds menu number 1, so print 1. The sequence becomes 15,3.

Sample Input 2

7
1 3
1 1
1 4
1 1
1 5
1 9
1 2

Sample Output 2

Note that there may be no queries of the second type.

Problem Statement

Given is a string S consisting of lowercase English letters. Determine whether adding some number of a's (possibly zero) at the beginning of S can make it a palindrome.

Here, a string of length N, A=A_1A_2\ldots A_N, is said to be a palindrome when A_i=A_{N+1-i} for every 1\leq i\leq N.

Constraints

• 1 \leq \lvert S \rvert \leq 10^6
• S consists of lowercase English letters.

Sample Input 1

kasaka

Sample Output 1

Yes

By adding one a at the beginning of kasaka, we have akasaka, which is a palindrome, so Yes should be printed.

Sample Input 2

atcoder

Sample Output 2

No

Adding any number of a's at the beginning of atcoder does not make it a palindrome.

Sample Input 3

php

Sample Output 3

Yes

php itself is a palindrome. Adding zero a's at the beginning of S is allowed, so Yes should be printed.

Problem Statement

For a non-negative integer K, we define a level-K carpet as follows:

• A level-0 carpet is a 1 \times 1 grid consisting of a single black cell.
• For K > 0, a level-K carpet is a 3^K \times 3^K grid. When this grid is divided into nine 3^{K-1} \times 3^{K-1} blocks:
  • The central block consists entirely of white cells.
  • The other eight blocks are level-(K-1) carpets.

You are given a non-negative integer N.
Print a level-N carpet according to the specified format.

Constraints

• 0 \leq N \leq 6
• N is an integer.

Sample Input 1

1

Sample Output 1

###
#.#
###

A level-1 carpet is a 3 \times 3 grid as follows:

When output according to the specified format, it looks like the sample output.

Sample Input 2

2

Sample Output 2

#########
#.##.##.#
#########
###...###
#.#...#.#
###...###
#########
#.##.##.#
#########

A level-2 carpet is a 9 \times 9 grid.

Problem Statement

There are N ants on a number line, labeled 1 to N. Ant i (1 \leq i \leq N) starts at coordinate X_i and faces either a positive or negative direction. Initially, all ants are at distinct coordinates. The direction each ant is facing is represented by a binary string S of length N, where ant i is facing the negative direction if S_i is 0 and the positive direction if S_i is 1.

Let the current time be 0, and the ants move in their respective directions at a speed of 1 unit per unit time for (T+0.1) units of time until time (T+0.1). If multiple ants reach the same coordinate, they pass through each other without changing direction or speed. After (T+0.1) units of time, all ants stop.

Find the number of pairs (i, j) such that 1 \leq i < j \leq N and ants i and j pass each other from now before time (T+0.1).

Constraints

• 2 \leq N \leq 2 \times 10^{5}
• 1 \leq T \leq 10^{9}
• S is a string of length N consisting of 0 and 1.
• -10^{9} \leq X_i \leq 10^{9} (1 \leq i \leq N)
• X_i \neq X_j (1 \leq i < j \leq N)
• N, T, and X_i (1 \leq i \leq N) are integers.

Sample Input 1

6 3
101010
-5 -1 0 1 2 4

Sample Output 1

5

The following five pairs of ants pass each other:

• Ant 3 and ant 4 pass each other at time 0.5.
• Ant 5 and ant 6 pass each other at time 1.
• Ant 1 and ant 2 pass each other at time 2.
• Ant 3 and ant 6 pass each other at time 2.
• Ant 1 and ant 4 pass each other at time 3.

No other pairs of ants pass each other, so print 5.

Sample Input 2

13 656320850
0100110011101
-900549713 -713494784 -713078652 -687818593 -517374932 -498415009 -472742091 -390030458 -379340552 -237481538 -44636942 352721061 695864366

Sample Output 2

14

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects Vertices U_i and V_i. Vertex i has a positive integer A_i written on it.

You will repeat the following operation N times.

• Choose a Vertex x that is not removed yet, and remove Vertex x and all edges incident to Vertex x. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex x that are not removed yet.

We define the cost of the entire N operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

• 1 \le N \le 2 \times 10^5
• 0 \le M \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le U_i,V_i \le N
• The given graph is simple.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3

By performing the operations as follows, the maximum of the costs of the N operations can be 3.

• Choose Vertex 3. The cost is A_1=3.
• Choose Vertex 1. The cost is A_2+A_4=3.
• Choose Vertex 2. The cost is 0.
• Choose Vertex 4. The cost is 0.

The maximum of the costs of the N operations cannot be 2 or less, so the solution is 3.

Sample Input 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

Sample Output 2

1199

Problem Statement

You are given positive integers N, M, K, and a sequence of positive integers of length N, (C_1, C_2, \ldots, C_N). For each r = 0, 1, 2, \ldots, N-1, print the answer to the following problem.

There is a sequence of N colored balls. For i = 1, 2, \ldots, N, the color of the i-th ball from the beginning of the sequence is C_i. Additionally, there are M empty boxes numbered 1 to M.

Determine the total number of balls in the boxes after performing the following steps.

• First, perform the following operation r times.

  • Move the frontmost ball in the sequence to the end of the sequence.

• Then, repeat the following operation as long as at least one ball remains in the sequence.

  • If there is a box that already contains at least one but fewer than K balls of the same color as the frontmost ball in the sequence, put the frontmost ball into that box.
  • If there is no such box,
    • If there is an empty box, put the frontmost ball into the one with the smallest box number.
    • If there are no empty boxes, eat the frontmost ball without putting it into any box.

Constraints

• All input values are integers.
• 1 \leq N \leq 2 \times 10^5
• 1 \leq M, K \leq N
• 1 \leq C_i \leq N

Sample Input 1

7 2 2
1 2 3 5 2 5 4

Sample Output 1

3
3
3
4
4
3
2

For example, let us explain the procedure for r = 1. First, perform the operation "Move the frontmost ball in the sequence to the end of the sequence" once, and the sequence of ball colors becomes (2, 3, 5, 2, 5, 4, 1). Then, proceed with the operation of putting balls into boxes as follows:

• First operation: The color of the frontmost ball is 2. There is no box with at least one but fewer than two balls of color 2, so put the frontmost ball into the empty box with the smallest box number, box 1.
• Second operation: The color of the frontmost ball is 3. There is no box with at least one but fewer than two balls of color 3, so put the frontmost ball into the empty box with the smallest box number, box 2.
• Third operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
• Fourth operation: The color of the frontmost ball is 2. There is a box, box 1, with at least one but fewer than two balls of color 2, so put the frontmost ball into box 1.
• Fifth operation: The color of the frontmost ball is 5. There is no box with at least one but fewer than two balls of color 5 and no empty boxes, so eat the frontmost ball.
• Sixth operation: The color of the frontmost ball is 4. There is no box with at least one but fewer than two balls of color 4 and no empty boxes, so eat the frontmost ball.
• Seventh operation: The color of the frontmost ball is 1. There is no box with at least one but fewer than two balls of color 1 and no empty boxes, so eat the frontmost ball.

The final total number of balls in the boxes is 3, so the answer to the problem for r = 1 is 3.

Sample Input 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

Sample Output 2

14
14
14
14
13
13
13
11
8
9
9
11
13
14
14
14
14
14
14
13