Problem Statement

In AtCoder Country where Takahashi lives, there is a strange law that "a person who possesses A or more candies must possess B or more cookies."

Takahashi possesses C candies and D cookies. Determine whether Takahashi is violating this law.

Constraints

• 1\leq A,B,C,D \leq 100
• All input values are integers.

Sample Input 1

10 20 30 40

Sample Output 1

No

In AtCoder Country, there is a law that "a person who possesses 10 or more candies must possess 20 or more cookies."

Takahashi possesses 30 candies and 40 cookies, so he is not violating this law.

Sample Input 2

10 20 30 4

Sample Output 2

Yes

Sample Input 3

100 100 1 1

Sample Output 3

No

Problem Statement

You are given an N-character string S consisting of lowercase English letters.

Output the string of N-A-B characters obtained by removing the first A characters and the last B characters from S.

Constraints

• 1\le N\le20
• 0\le A
• 0\le B
• A+B\lt N
• S is a string of N characters consisting of lowercase English letters.
• N, A, and B are all integers.

Sample Input 1

7 1 3
atcoder

Sample Output 1

tco

Removing the first one character and the last three characters from atcoder gives tco.

Sample Input 2

1 0 0
a

Sample Output 2

a

The string to be output may be equal to S.

Sample Input 3

20 4 8
abcdefghijklmnopqrst

Sample Output 3

efghijkl

Problem Statement

In AtCoder City, N types of garbage are collected regularly. The i-th type of garbage (i=1,2,\dots,N) is collected on days when the date modulo q_i equals r_i.

Answer Q queries. In the j-th query (j=1,2,\dots,Q), given that the t_j-th type of garbage is put out on day d_j, answer the next day on which it will be collected.

Here, if the i-th type of garbage is put out on a day when that type of garbage is collected, then the garbage will be collected on the same day.

Constraints

• 1 \leq N \leq 100
• 0 \leq r_i < q_i \leq 10^9
• 1 \leq Q \leq 100
• 1 \leq t_j \leq N
• 1 \leq d_j \leq 10^9
• All input values are integers.

Sample Input 1

2
7 3
4 2
5
1 1
1 3
1 4
1 15
2 7

Sample Output 1

3
3
10
17
10

• 1st query: The 1st type of garbage is collected on day 3 for the first time after day 1.
• 2nd query: The 1st type of garbage is collected on day 3 for the first time after day 3.
• 3rd query: The 1st type of garbage is collected on day 10 for the first time after day 4.

Problem Statement

Consider an xy-plane. The positive direction of the x-axis is in the direction of east, and the positive direction of the y-axis is in the direction of north.
Takahashi is initially at point (x, y) = (0, 0) and facing east (in the positive direction of the x-axis).

You are given a string T = t_1t_2\ldots t_N of length N consisting of S and R. Takahashi will do the following move for each i = 1, 2, \ldots, N in this order.

• If t_i = S, Takahashi advances in the current direction by distance 1.
• If t_i = R, Takahashi turns 90 degrees clockwise without changing his position. As a result, Takahashi's direction changes as follows.
  • If he is facing east (in the positive direction of the x-axis) before he turns, he will face south (in the negative direction of the y-axis) after he turns.
  • If he is facing south (in the negative direction of the y-axis) before he turns, he will face west (in the negative direction of the x-axis) after he turns.
  • If he is facing west (in the negative direction of the x-axis) before he turns, he will face north (in the positive direction of the y-axis) after he turns.
  • If he is facing north (in the positive direction of the y-axis) before he turns, he will face east (in the positive direction of the x-axis) after he turns.

Print the coordinates Takahashi is at after all the steps above have been done.

Constraints

• 1 \leq N \leq 10^5
• N is an integer.
• T is a string of length N consisting of S and R.

Sample Input 1

4
SSRS

Sample Output 1

2 -1

Takahashi is initially at (0, 0) facing east. Then, he moves as follows.

1. t_1 = S, so he advances in the direction of east by distance 1, arriving at (1, 0).
2. t_2 = S, so he advances in the direction of east by distance 1, arriving at (2, 0).
3. t_3 = R, so he turns 90 degrees clockwise, resulting in facing south.
4. t_4 = S, so he advances in the direction of south by distance 1, arriving at (2, -1).

Thus, Takahashi's final position, (x, y) = (2, -1), should be printed.

Sample Input 2

20
SRSRSSRSSSRSRRRRRSRR

Sample Output 2

0 1

Problem Statement

You are given simple undirected graphs G and H, each with N vertices: vertices 1, 2, \ldots, N. Graph G has M_G edges, and its i-th edge (1\leq i\leq M_G) connects vertices u_i and v_i. Graph H has M_H edges, and its i-th edge (1\leq i\leq M_H) connects vertices a_i and b_i.

You can perform the following operation on graph H any number of times, possibly zero.

• Choose a pair of integers (i,j) satisfying 1\leq i<j\leq N. Pay A_{i,j} yen, and if there is no edge between vertices i and j in H, add one; if there is, remove it.

Find the minimum total cost required to make G and H isomorphic.

Constraints

• 1\leq N\leq8
• 0\leq M _ G\leq\dfrac{N(N-1)}2
• 0\leq M _ H\leq\dfrac{N(N-1)}2
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
• (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
• 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
• (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
• 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

5
4
1 2
2 3
3 4
4 5
4
1 2
1 3
1 4
1 5
3 1 4 1
5 9 2
6 5
3

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on H to make it isomorphic to G at a cost of 9 yen.

• Choose (i,j)=(1,3). There is an edge between vertices 1 and 3 in H, so pay 1 yen to remove it.
• Choose (i,j)=(2,5). There is no edge between vertices 2 and 5 in H, so pay 2 yen to add it.
• Choose (i,j)=(1,5). There is an edge between vertices 1 and 5 in H, so pay 1 yen to remove it.
• Choose (i,j)=(3,5). There is no edge between vertices 3 and 5 in H, so pay 5 yen to add it.

After these operations, H becomes:

You cannot make G and H isomorphic at a cost less than 9 yen, so print 9.

Sample Input 2

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

Sample Output 2

3

For example, performing the operations (i,j)=(2,3),(2,4),(3,4) on H will make it isomorphic to G.

Sample Input 3

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

Sample Output 3

5

For example, performing the operation (i,j)=(4,5) once will make G and H isomorphic.

Sample Input 4

2
0
0
371

Sample Output 4

0

Note that G and H may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

Sample Output 5

21214