Problem Statement

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

Here, we define the number of dots in a lowercase English letter as follows:

• If the lowercase English letter is i or j: 1 dot
• If the lowercase English letter is neither i nor j: 0 dots

Find the sum of the numbers of dots over all characters in S.

Constraints

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

Sample Input 1

aiiaj

Sample Output 1

3

The numbers of dots in a, i, i, a, j are 0, 1, 1, 0, 1, respectively.

We have 0 + 1 + 1 + 0 + 1 = 3, so print 3.

Sample Input 2

abcedfgh

Sample Output 2

0

Sample Input 3

jjjjjj

Sample Output 3

6

Problem Statement

You are given N strings.

The i-th string S_i (1 \leq i \leq N) is either Takahashi or Aoki.

How many i are there such that S_i is equal to Takahashi?

Constraints

• 1 \leq N \leq 100
• N is an integer.
• Each S_i is Takahashi or Aoki. (1 \leq i \leq N)

Sample Input 1

3
Aoki
Takahashi
Takahashi

Sample Output 1

2

S_2 and S_3 are equal to Takahashi, while S_1 is not.

Therefore, print 2.

Sample Input 2

2
Aoki
Aoki

Sample Output 2

0

It is possible that no S_i is equal to Takahashi.

Sample Input 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

Sample Output 3

7

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 100
• N and A_i are integers.
• S_i is L or R.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

11

For example, the performance can be done as follows:

• Initially, place the left hand on key 3 and the right hand on key 6.
• Press key 3 with the left hand.
• Press key 6 with the right hand.
• Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
• Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
• Press key 9 with the left hand.
• Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

3
2 L
2 L
100 L

Sample Output 2

98

Sample Input 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

Sample Output 3

188

Problem Statement

The company where Takahashi works has N employees, each assigned an employee number from 1, 2, \dots, N. There are M departments in the company, called departments 1, 2, \dots, M.

Employee i belongs to department A_i this term and will belong to department B_i next term.

For each of departments 1, 2, \dots, M, find the number of members next term minus the number of members this term.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq A_i \leq M
• 1 \leq B_i \leq M
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
-1
-1
1

• For department 1: this term, one employee (employee number 1) belongs; next term, two employees (employee numbers 2, 3) belong.
• For department 2: this term, three employees (employee numbers 2, 4, 5) belong; next term, two employees (employee numbers 1, 4) belong.
• For department 3: this term, one employee (employee number 3) belongs; next term, no one belongs.
• For department 4: this term, no one belongs; next term, one employee (employee number 5) belongs.

Sample Input 2

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

Sample Output 2

0
4
-5
1
0

Problem Statement

2N players, with ID numbers 1 through 2N, will participate in a rock-scissors-paper contest.

The contest has M rounds. Each round has N one-on-one matches, where each player plays in one of them.

For each i=0, 1, \ldots, M, the players' ranks at the end of the i-th round are determined as follows.

• A player with more wins in the first i rounds ranks higher.
• Ties are broken by ID numbers: a player with a smaller ID number ranks higher.

Additionally, for each i=1, \ldots, M, the matches in the i-th round are arranged as follows.

• For each k=1, 2, \ldots, N, a match is played between the players who rank (2k-1)-th and 2k-th at the end of the (i-1)-th round.

In each match, the two players play a hand just once, resulting in one player's win and the other's loss, or a draw.

Takahashi, who can foresee the future, knows that Player i will play A_{i, j} in their match in the j-th round, where A_{i,j} is G, C, or P.
Here, G stands for rock, C stands for scissors, and P stands for paper. (These derive from Japanese.)

Find the players' ranks at the end of the M-th round.

Constraints

• 1 \leq N \leq 50
• 1 \leq M \leq 100
• A_{i,j} is G, C, or P.

Sample Input 1

2 3
GCP
PPP
CCC
PPC

Sample Output 1

3
1
2
4

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. Player 3 wins the former, and Player 1 wins the latter.
In the third round, matches are played between Players 3 and 1, and between Players 2 and 4. Player 3 wins the former, and Player 4 wins the latter.
Therefore, in the end, the players are ranked in the following order: 3,1,2,4, from highest to lowest.

Sample Input 2

2 2
GC
PG
CG
PP

Sample Output 2

1
2
3
4

In the first round, matches are played between Players 1 and 2, and between Players 3 and 4. Player 2 wins the former, and Player 3 wins the latter.
In the second round, matches are played between Players 2 and 3, and between Players 1 and 4. The former is drawn, and Player 1 wins the latter.
Therefore, in the end, the players are ranked in the following order: 1,2,3,4, from highest to lowest.

Problem Statement

A positive integer X is called a good integer if and only if it satisfies the following condition:

• There exists a pair of positive integers (a,b) such that X = 2^a \times b^2.

For example, 400 is a good integer because 400 = 2^2 \times 10^2.

Given a positive integer N, find the number of good integers between 1 and N, inclusive.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

20

Sample Output 1

5

There are five good integers between 1 and 20: 2, 4, 8, 16, and 18.
Thus, print 5.

Sample Input 2

400

Sample Output 2

24

Sample Input 3

1234567890

Sample Output 3

42413

Note that the input might not fit in a 32-bit integer type.

Problem Statement

You are given a string S of length N consisting of 0 and 1.

A string T of length N consisting of 0 and 1 is a good string if and only if it satisfies the following condition:

• There is exactly one integer i such that 1 \leq i \leq N - 1 and the i-th and (i + 1)-th characters of T are the same.

For each i = 1,2,\ldots, N, you can choose whether or not to perform the following operation once:

• If the i-th character of S is 0, replace it with 1, and vice versa. The cost of this operation, if performed, is C_i.

Find the minimum total cost required to make S a good string.

Constraints

• 2 \leq N \leq 2 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 1 \leq C_i \leq 10^9
• N and C_i are integers.

Sample Input 1

5
00011
3 9 2 6 4

Sample Output 1

7

Performing the operation for i = 1, 5 and not performing it for i = 2, 3, 4 makes S = 10010, which is a good string. The cost incurred in this case is 7, and it is impossible to make S a good string for less than 7, so print 7.

Sample Input 2

4
1001
1 2 3 4

Sample Output 2

0

Sample Input 3

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

Sample Output 3

2286846953

Problem Statement

There are N balls lined up in a row.
The i-th ball from the left is of color C_i and has a value of V_i.

Takahashi wants to remove exactly K balls from this row so that no two adjacent balls have the same color when arranging the remaining balls without changing the order. Additionally, under that condition, he wants to maximize the total value of the balls remaining in the row.

Determine if Takahashi can remove K balls so that no two adjacent balls in the remaining row have the same color. If it is possible, find the maximum possible total value of the remaining balls.

Constraints

• 1\leq K<N\leq 2\times 10^5
• K\leq 500
• 1\leq C_i\leq N
• 1\leq V_i\leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

10

After removing the 3-rd and 5-th balls from the left, the remaining balls are of colors 1, 3, 1 from left to right, so no two adjacent balls have the same color, satisfying the condition.
The total value of the remaining balls is V_1+V_2+V_4=1+5+4=10.
There are other ways to remove two balls from the five balls so that no two adjacent balls have the same color, but the total value of the remaining balls is maximized when removing the 3-rd and 5-th balls.

Hence, print 10.

Sample Input 2

3 1
1 10
1 10
1 10

Sample Output 2

-1

No matter how you remove one ball, balls of color 1 will end up next to each other.
Hence, print -1.

Sample Input 3

3 1
1 1
2 2
3 3

Sample Output 3

5

Note that exactly K balls must be removed.

Problem Statement

You are given N strings S _ 1,S _ 2,\ldots,S _ N. S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters, and the strings are pairwise distinct.

Taro the First and Jiro the Second play a word-chain game. In this game, the two players take alternating turns, with Taro the First going first. In each player's turn, the player chooses an integer i\ (1\leq i\leq N), which should satisfy the following two conditions:

• i is different from any integer chosen by the two players so far since the game started;
• the current turn is the first turn of the game, or the last character of S_j equals the first character of S_i, where j is the last integer chosen.

The player who is unable to choose a conforming i loses; the other player wins.

Determine which player will win if the two players play optimally.

Constraints

• 1 \leq N \leq 16
• N is an integer.
• S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters.
• S _ i\neq S _ j\ (1\leq i\lt j\leq N)

Sample Input 1

6
enum
float
if
modint
takahashi
template

Sample Output 1

First

For example, the game progresses as follows. Note that the two players may not be playing optimally in this example.

• Taro the First chooses i=3. S _ i=if.
• Jiro the Second chooses i=2. S _ i=float, and the last character of if equals the first character of float.
• Taro the First chooses i=5. S _ i=takahashi, and the last character of float equals the first character of takahashi.
• Jiro the Second is unable to choose i\neq2,3,5 such that S _ i starts with i, so he loses.

In this case, Taro the First wins.

Sample Input 2

10
catch
chokudai
class
continue
copy
exec
havoc
intrinsic
static
yucatec

Sample Output 2

Second

Sample Input 3

16
mnofcmzsdx
lgeowlxuqm
ouimgdjxlo
jhwttcycwl
jbcuioqbsj
mdjfikdwix
jhvdpuxfil
peekycgxco
sbvxszools
xuuqebcrzp
jsciwvdqzl
obblxzjhco
ptobhnpfpo
muizaqtpgx
jtgjnbtzcl
sivwidaszs

Sample Output 3

First