Problem Statement

You are playing a game called Guru Guru Gururin. In this game, you can move with the vehicle called Gururin. There are two commands you can give to Gururin: R and L. When R is sent, Gururin rotates clockwise by 90 degrees. Otherwise, when L is sent, Gururin rotates counterclockwise by 90 degrees.

During the game, you noticed that Gururin obtains magical power by performing special commands. In short, Gururin obtains magical power every time when it performs one round in the clockwise direction from north to north. In more detail, the conditions under which magical power can be obtained is as follows.

• At the beginning of the special commands, Gururin faces north.
• At the end of special commands, Gururin faces north.
• Except for the beginning and the end of special commands, Gururin does not face north.
• During the special commands, Gururin faces north, east, south, and west one or more times, respectively, after the command of R.

At the beginning of the game, Gururin faces north. For example, if the sequence of commands Gururin received in order is RRRR or RRLRRLRR, Gururin can obtain magical power. Otherwise, if the sequence of commands is LLLL or RLLR, Gururin cannot obtain magical power.

Your task is to calculate how many times Gururin obtained magical power throughout the game. In other words, given the sequence of the commands Gururin received, calculate how many special commands exists in it.

---

Input

The input consists of a single test case in the format below.

$S$

The first line consists of a string $S$, which represents the sequence of commands Gururin received. S consists of L and R. The length of $S$ is between $1$ and $10^3$ inclusive.

Output

Print the number of times Gururin obtained magical power throughout the game in one line.

---

Sample Input 1

RRRRLLLLRRRR

Output for Sample Input 1

2

---

Sample Input 2

RLLRLLLLRRRLLLRRR

Output for Sample Input 2

0

---

Sample Input 3

LR

Output for Sample Input 3

0

---

Sample Input 4

RRLRRLRRRRLRRLRRRRLRRLRRRRLRRLRR

Output for Sample Input 4

4

Problem Statement

In the Jambo Amusement Garden (JAG), you sell colorful drinks consisting of multiple color layers. This colorful drink can be made by pouring multiple colored liquids of different density from the bottom in order.

You have already prepared several colored liquids with various colors and densities. You will receive a drink request with specified color layers. The colorful drink that you will serve must satisfy the following conditions.

• You cannot use a mixed colored liquid as a layer. Thus, for instance, you cannot create a new liquid with a new color by mixing two or more different colored liquids, nor create a liquid with a density between two or more liquids with the same color by mixing them.
• Only a colored liquid with strictly less density can be an upper layer of a denser colored liquid in a drink. That is, you can put a layer of a colored liquid with density $x$ directly above the layer of a colored liquid with density $y$ if $x < y$ holds.

Your task is to create a program to determine whether a given request can be fulfilled with the prepared colored liquids under the above conditions or not.

---

Input

The input consists of a single test case in the format below.

$N$ $C_1$ $D_1$ $\vdots$ $C_N$ $D_N$ $M$ $O_1$ $\vdots$ $O_M$

The first line consists of an integer $N$ ($1 \le N \le 10^5$), which represents the number of the prepared colored liquids. The following $N$ lines consists of $C_i$ and $D_i$ ($1 \leq i \leq N$). $C_i$ is a string consisting of lowercase alphabets and denotes the color of the $i$-th prepared colored liquid. The length of $C_i$ is between $1$ and $20$ inclusive. $D_i$ is an integer and represents the density of the $i$-th prepared colored liquid. The value of $D_i$ is between $1$ and $10^5$ inclusive. The ($N+2$)-nd line consists of an integer $M$ ($1 \leq M \leq 10^5$), which represents the number of color layers of a drink request. The following $M$ lines consists of $O_i$ ($1 \leq i \leq M$). $O_i$ is a string consisting of lowercase alphabets and denotes the color of the $i$-th layer from the top of the drink request. The length of $O_i$ is between $1$ and $20$ inclusive.

Output

If the requested colorful drink can be served by using some of the prepared colored liquids, print Yes. Otherwise, print No.

---

Sample Input 1

2
white 20
black 10
2
black
white

Output for Sample Input 1

Yes

---

Sample Input 2

2
white 10
black 10
2
black
white

Output for Sample Input 2

No

---

Sample Input 3

2
white 20
black 10
2
black
orange

Output for Sample Input 3

No

---

Sample Input 4

3
white 10
red 20
white 30
3
white
red
white

Output for Sample Input 4

Yes

---

Sample Input 5

4
red 3444
red 3018
red 3098
red 3319
4
red
red
red
red

Output for Sample Input 5

Yes

Problem Statement

Santa is going to pack gifts into a bag for a family. There are $N$ kinds of gifts. The size and the price of the $i$-th gift ($1 \le i \le N$) are $s_i$ and $p_i$, respectively. The size of the bag is $C$, thus Santa can pack gifts so that the total size of the gifts does not exceed $C$. Children are unhappy if they are given multiple items of the same kind gift, so Santa has to choose at most one gift of the same kind per child.

In addition, if a child did not receive a gift that the other children in the same family receive, he/she will complain about that. Hence Santa must distribute gifts fairly to all the children of a family, by giving the same set of gifts to each child. In other words, for a family with $k$ children, Santa must pack zero or $k$ items for each kind of gifts. Santa gives one bag to one family, therefore, the total size of the gifts for each family does not exceed $C$.

Santa wants to maximize the total price of packed items for a family but does not know the number of children in the family he is going to visit yet. The number seems at most $M$. To prepare all the possible cases, calculate the maximum total price of items for a family with $k$ children for each $1 \le k \le M$.

---

Input

The input consists of a single test case in the following format.

$C$ $N$ $M$ $s_1$ $p_1$ ... $s_N$ $p_N$

The first line contains three integers $C$, $N$ and $M$, where $C$ ($1 \le C \le 10^4$) is the size of the bag, $N$ ($1 \le N \le 10^4$) is the number of kinds of the gifts, and $M$ ($1 \le M \le 10^4$) is the maximum number of children in the family. The $i$-th line of the following $N$ lines contains two integers $s_i$ and $p_i$ ($1 \le s_i, p_i \le 10^4$), where $s_i$ and $p_i$ are the size and the price of the $i$-th gift, respectively.

Output

The output should consist of $M$ lines. In the $k$-th line, print the maximum total price of gifts for a family with $k$ children.

---

Sample Input 1

6 3 2
1 2
2 10
3 5

Output for Sample Input 1

17
24

---

Sample Input 2

200 5 5
31 41
59 26
53 58
97 93
23 84

Output for Sample Input 2

235
284
375
336
420

---

Sample Input 3

1 1 2
1 1

Output for Sample Input 3

1
0

---

Sample Input 4

2 2 2
1 1
2 100

Output for Sample Input 4

100
2

Problem Statement

As an English learner, sometimes you cannot remember the entire spelling of English words perfectly, but you can only remember their prefixes and suffixes. For example, you may want to use a word which begins with appr and ends with iate, but forget the middle part of the word. It may be appreciate, appropriate, or something like them.

By using an ordinary dictionary, you can look up words beginning with a certain prefix, but it is inconvenient for further filtering words ending with a certain suffix. Thus it is helpful to achieve dictionary functionality which can be used for finding words with a given prefix and suffix. In the beginning, let's count the number of such words instead of explicitly listing them.

More formally, you are given a list of $N$ words. Next, you are given $Q$ queries consisting of two strings. Your task is to write a program which outputs the number of words with the prefix and suffix for each query in the given list.

---

Input

The input consists of a single test case in the following format.

$N$ $Q$ $w_1$ ... $w_N$ $p_1$ $s_1$ ... $p_Q$ $s_Q$

The first line contains two integers $N$ and $Q$, where $N$ ($1 \le N \le 10^5$) is the number of words in the list, and $Q$ ($1 \le Q \le 10^5$) is the number of queries. The $i$-th line of the following $N$ lines contains a string $w_i$. The $i$-th of the following $Q$ lines contains two strings $p_i$ and $s_i$, which are a prefix and suffix of words to be searched, respectively.

You can assume the followings:

• All the strings in an input are non-empty and consist only of lowercase English letters.
• The total length of input strings does not exceed $2{,}500{,}000$.
• Words in the given list are unique: $w_i \neq w_j$ if $i \neq j$.
• Pairs of a prefix and suffix are unique: $(p_i, s_i) \neq (p_j, s_j)$ if $i \neq j$.

Output

For each query, output the number of words with a given prefix and suffix in the given list per a line.

---

Sample Input 1

6 7
appreciate
appropriate
acceptance
ace
acm
acetylene
appr iate
a e
a a
ac ce
ace e
acceptance acceptance
no match

Output for Sample Input 1

2
5
0
2
2
1
0

---

Sample Input 2

5 5
d
dd
ddd
dddd
ddddd
d d
dd dd
ddd ddd
d dddd
ddddd dd

Output for Sample Input 2

5
4
3
2
1

---

Sample Input 3

7 4
connected
disconnected
graph
directed
diameter
distance
minor
c ed
di ed
dis ed
dis e

Output for Sample Input 3

1
2
1
1

Problem Statement

Fallen angel Yohane plans to draw a magic symbol composed of triangles on the earth. By casting some magic spell on the symbol, she will obtain magic power; this is the purpose for which she will draw a magic symbol. The magic power yielded from the magic symbol is determined only by the common area of all the triangles. Suppose the earth is a two-dimensional plane and the vertices of the triangles are points on the plane. Yohane has already had a design of the magic symbol, i.e. the positions, sizes, shapes of the triangles. However, she does not know how much magic power will be obtained from the symbol. Your task as a familiar of the fallen angel is to write a program calculating the common area of given triangles on a two-dimensional plane.

---

Input

The input consists of a single test case in the following format.

$N$ $x_{1,1}$ $y_{1,1}$ $x_{1,2}$ $y_{1,2}$ $x_{1,3}$ $y_{1,3}$ ... $x_{N,1}$ $y_{N,1}$ $x_{N,2}$ $y_{N,2}$ $x_{N,3}$ $y_{N,3}$

The first line contains an integer $N$, which is the number of triangles ($1 \le N \le 10^5$). The $i$-th line of the following $N$ lines contains six integers $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, $y_{i,2}$, $x_{i,3}$, and $y_{i,3}$, where $(x_{i, j}, y_{i, j})$ is the coordinate of the $j$-th vertex of the $i$-th triangle ($-1{,}000 \le x_{i, j}, y_{i, j} \le 1{,}000$).

You can assume the followings:

• Every triangle has a positive area.
• The vertices of every triangle are in the counter-clockwise order.

Output

Output the common area of given triangles in a line. The output can contain an absolute or relative error no more than $10^{−6}$.

---

Sample Input 1

2
0 0 2 0 0 2
0 1 2 1 0 3

Output for Sample Input 1

0.5

---

Sample Input 2

2
0 0 100 0 50 100
50 -50 100 50 0 50

Output for Sample Input 2

3125

---

Sample Input 3

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

Output for Sample Input 3

0.5

Problem Statement

Alice: "Hi, Bob! Let's play Nim!"

Bob: "Are you serious? I don't want to play it. I know how to win the game."

Alice: "Right, there is an algorithm to calculate the optimal move using XOR. How about changing the rule so that a player loses a game if he or she makes the XOR to $0$?"

Bob: "It sounds much better now, but I suspect you know the surefire way to win."

Alice: "Do you wanna test me?"

This game is defined as follows.

1. The game starts with $N$ heaps where the $i$-th of them consists of $a_i$ stones.
2. A player takes any positive number of stones from any single one of the heaps in one move.
3. Alice moves first. The two players alternately move.
4. If the XOR sum, $a_1$ XOR $a_2$ XOR $\cdots$ XOR $a_N$, of the numbers of remaining stones of these heaps becomes $0$ as a result of a player's move, the player loses.

Your task is to find which player will win if they do the best move.

---

Input

The input consists of a single test case in the format below.

$N$ $a_{1}$ $\vdots$ $a_{N}$

The first line contains an integer $N$ which is the number of the heaps ($1 \le N \le 10^5$). Each of the following $N$ lines gives the number of stones in each heap ($1 \le a_i \le 10^9$).

Output

Output the winner, Alice or Bob, when they do the best move.

---

Sample Input 1

2
1
1

Output for Sample Input 1

Alice

---

Sample Input 2

5
1
2
3
4
5

Output for Sample Input 2

Bob

---

Sample Input 3

10
1
2
3
4
5
6
7
8
9
10

Output for Sample Input 3

Alice

---

In the first example, the XOR sum is 0 in the initial state, but the game is going because nobody moves yet. First Alice takes a stone and the XOR sum becomes 1, then Bob takes the last stone and the XOR sum becomes 0. Therefore, Alice will win, and Bob will lose.

Problem Statement

You are given an integer $N$ and a string consisting of + and digits. You are asked to transform the string into a valid formula whose calculation result is smaller than or equal to $N$ by modifying some characters. Here, you replace one character with another character any number of times, and the converted string should still consist of + and digits. Note that leading zeros and unary positive are prohibited.

For instance, 0123+456 is assumed as invalid because leading zero is prohibited. Similarly, +1+2 and 2++3 are also invalid as they each contain a unary expression. On the other hand, 12345, 0+1+2 and 1234+0+0 are all valid.

Your task is to find the minimum number of the replaced characters. If there is no way to make a valid formula smaller than or equal to $N$, output $-1$ instead of the number of the replaced characters.

---

Input

The input consists of a single test case in the following format.

$N$ $S$

The first line contains an integer $N$, which is the upper limit of the formula ($1 \le N \le 10^9$). The second line contains a string $S$, which consists of + and digits and whose length is between $1$ and $1{,}000$, inclusive. Note that it is not guaranteed that initially $S$ is a valid formula.

Output

Output the minimized number of the replaced characters. If there is no way to replace, output $-1$ instead.

---

Sample Input 1

100
+123

Output for Sample Input 1

2

---

Sample Input 2

10
+123

Output for Sample Input 2

4

---

Sample Input 3

1
+123

Output for Sample Input 3

-1

---

Sample Input 4

10
++1+

Output for Sample Input 4

2

---

Sample Input 5

2000
1234++7890

Output for Sample Input 5

2

---

In the first example, you can modify the first two characters and make a formula 1+23, for instance. In the second example, you should make 0+10 or 10+0 by replacing all the characters. In the third example, you cannot make any valid formula less than or equal to $1$.

Problem Statement

You are given $N$ distinct points on the 2-D plane. For each point, you are going to make a single circle whose center is located at the point. Your task is to maximize the sum of perimeters of these $N$ circles so that circles do not overlap each other. Here, "overlap" means that two circles have a common point which is not on the circumference of at least either of them. Therefore, the circumferences can be touched. Note that you are allowed to make a circle with radius $0$.

---

Input

The input consists of a single test case in the following format.

$N$ $x_{1}$ $y_{1}$ $\vdots$ $x_{N}$ $y_{N}$

The first line contains an integer $N$, which is the number of points ($2 \le N \le 200$). Each of the following $N$ lines gives the coordinates of a point. Integers $x_i$ and $y_i$ ($−100 ≤ x_i, y_i ≤ 100$) in the $i$-th line of them give the $x$- and $y$-coordinates, respectively, of the $i$-th point. These points are distinct, in other words, $(x_i, y_i) \ne (x_j, y_j)$ is satisfied if $i$ and $j$ are different.

Output

Output the maximized sum of perimeters. The output can contain an absolute or a relative error no more than $10^{-6}$.

---

Sample Input 1

3
0 0
3 0
5 0

Output for Sample Input 1

31.415926535

---

Sample Input 2

3
0 0
5 0
0 5

Output for Sample Input 2

53.630341225

---

Sample Input 3

9
91 -18
13 93
73 -34
15 2
-46 0
69 -42
-23 -13
-87 41
38 68

Output for Sample Input 3

1049.191683488

Problem Statement

You received a card with an integer $S$ and a multiplication table of infinite size. All the elements in the table are integers, and an integer at the $i$-th row from the top and the $j$-th column from the left is $A_{i, j} = i \times j$ ($i, j \ge 1$). The table has infinite size, i.e., the number of the rows and the number of the columns are infinite.

You love rectangular regions of the table in which the sum of numbers is $S$. Your task is to count the number of integer tuples $(a, b, c, d)$ that satisfies $1 \leq a \leq b, 1 \leq c \leq d$ and $\sum_{i=a}^{b} \sum_{j=c}^{d} A_{i,j} = S$.

---

Input

The input consists of a single test case of the following form.

$S$

The first line consists of one integer $S$ ($1 \leq S \leq 10^5$), representing the summation of rectangular regions you have to find.

Output

Print the number of rectangular regions whose summation is $S$ in one line.

---

Sample Input 1

25

Output for Sample Input 1

10

---

Sample Input 2

1

Output for Sample Input 2

1

---

Sample Input 3

5

Output for Sample Input 3

4

---

Sample Input 4

83160

Output for Sample Input 4

5120

Problem Statement

Fox Jiro is one of the staffs of the ACM-ICPC 2018 Asia Yokohama Regional Contest and is responsible for designing the network for the venue of the contest. His network consists of $N$ computers, which are connected by $M$ cables. The $i$-th cable connects the $a_i$-th computer and the $b_i$-th computer, and it carries data in both directions. Your team will use the $S$-th computer in the contest, and a judge server is the $T$-th computer.

He decided to adjust the routing algorithm of the network to maximize the performance of the contestants through the magical power of prime numbers. In this algorithm, a packet (a unit of data carried by the network) is sent from your computer to the judge server passing through the cables a prime number of times if possible. If it is impossible, the contestants cannot benefit by the magical power of prime numbers. To accomplish this target, a packet is allowed to pass through the same cable multiple times.

You decided to write a program to calculate the minimum number of times a packet from $S$ to $T$ needed to pass through the cables. If the number of times a packet passes through the cables cannot be a prime number, print $-1$.

---

Input

The input consists of a single test case, formatted as follows.

$N$ $M$ $S$ $T$ $a_1$ $b_1$ $\vdots$ $a_M$ $b_M$

The first line consists of four integers $N$, $M$, $S$, and $T$ ($2 \leq N \leq 10^5$, $1 \leq M \leq 10^5$, $1 \leq S, T \leq N$, $S \neq T$). The $i$-th line of the following $M$ lines consists of two integers $a_i$ and $b_i$ ($1 \leq a_i < b_i \leq N$), which means the $i$-th cables connects the $a_i$-th computer and the $b_i$-th computer in the network. You can assume that the network satisfies the following conditions.

• The network has no multi-edge, i.e., $(a_i, b_i) \neq (a_j, b_j)$ for all $i$, $j$ ($1 \leq i \lt j \leq M$).
• The packets from $N$ computers are reachable to $T$ by passing through some number of cables. The number is not necessarily a prime.

Output

If there are ways such that the number of times a packet sent from $S$ to $T$ passes through the cables is a prime number, print the minimum prime number of times in one line. Otherwise, print $-1$.

---

Sample Input 1

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

Output for Sample Input 1

3

---

Sample Input 2

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

Output for Sample Input 2

-1

---

Sample Input 3

2 1 1 2
1 2

Output for Sample Input 3

3

---

Sample Input 4

3 3 1 2
1 2
1 3
2 3

Output for Sample Input 4

2

Problem Statement

For skilled programmers, it is very easy to implement a sorting function. Moreover, they often avoid full sorting to reduce computation time if it is not necessary. Here, we consider "rough sorting" which sorts an array except for some pairs of elements. More formally, we define an array is "$K$-roughly sorted" if an array is sorted except that at most $K$ pairs are in reversed order. For example, 1 3 2 4 is 1-roughly sorted because $(3, 2)$ is only the reversed pair. In the same way, 1 4 2 3 is 2-roughly sorted because $(4, 2)$ and $(4, 3)$ are reversed.

Considering rough sorting by exchanging adjacent elements repeatedly, you need less number of swaps than full sorting. For example, 4 1 2 3 needs three exchanges for full sorting, but you only need to exchange once for 2-rough sorting.

Given an array and an integer $K$, your task is to find the result of the $K$-rough sorting with a minimum number of exchanges. If there are several possible results, you should output the lexicographically minimum result. Here, the lexicographical order is defined by the order of the first different elements.

---

Input

The input consists of a single test case in the following format.

$N$ $K$ $x_{1}$ $\vdots$ $x_{N}$

The first line contains two integers $N$ and $K$. The integer $N$ is the number of the elements of the array ($1 \le N \le 10^5$). The integer $K$ gives how many reversed pairs are allowed ($1 \le K \le 10^9$). Each of the following $N$ lines gives the element of the array. The array consists of the permutation of $1$ to $N$, therefore $1 \le x_i \le N$ and $x_i \ne x_j$ ($i \ne j$) are satisfied.

Output

The output should contain $N$ lines. The $i$-th line should be the $i$-th element of the result of the $K$-rough sorting. If there are several possible results, you should output the minimum result with the lexicographical order.

---

Sample Input 1

3 1
3
2
1

Output for Sample Input 1

1
3
2

---

Sample Input 2

3 100
3
2
1

Output for Sample Input 2

3
2
1

---

Sample Input 3

5 3
5
3
2
1
4

Output for Sample Input 3

1
3
5
2
4

---

Sample Input 4

5 3
1
2
3
4
5

Output for Sample Input 4

1
2
3
4
5

---

In the last example, the input array is already sorted, which means the input is already a 3-roughly sorted array and no swapping is needed.