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.