Problem Statement

Takahashi will have N penalty kicks in a soccer match.

For the i-th penalty kick, he will fail if i is a multiple of 3, and succeed otherwise.

Print the results of his penalty kicks.

Constraints

• 1 \leq N \leq 100
• All inputs are integers.

Sample Input 1

7

Sample Output 1

ooxooxo

Takahashi fails the third and sixth penalty kicks, so the third and sixth characters will be x.

Sample Input 2

9

Sample Output 2

ooxooxoox

Problem Statement

You are given a string S consisting of uppercase English letters. Here, the length of S is odd.

Print the string obtained by deleting the middle character of S. The middle character of S is the \frac{L+1}{2}-th character of S, where L is the length of S.

Constraints

• S is a string consisting of uppercase English letters.
• The length of S is an odd number between 3 and 9, inclusive.

Sample Input 1

ABCDE

Sample Output 1

ABDE

The middle character of ABCDE is the 3-rd character C, so print ABDE.

Sample Input 2

OOO

Sample Output 2

OO

Sample Input 3

ATCODER

Sample Output 3

ATCDER

Problem Statement

I begin with T and end with T, and I am full of T. What am I?

For a string t, define the filling rate as follows:

• If the first and last characters of t are both t and |t| \geq 3: Let x be the number of t in t. Then the filling rate of t is \displaystyle\frac{x-2}{|t|-2}, where |t| denotes the length of t.
• Otherwise: the filling rate of t is 0.

You are given a string S. Find the maximum possible filling rate of a substring of S.

Constraints

• 1 \leq |S| \leq 100
• S is a string consisting of lowercase English letters.

Sample Input 1

attitude

Sample Output 1

0.50000000000000000

ttit is a substring of S, and its filling rate is \displaystyle\frac{3-2}{4-2} = \frac{1}{2}.

There is no substring with a filling rate greater than \frac{1}{2}, so the answer is \frac{1}{2}.

Sample Input 2

ottottott

Sample Output 2

0.66666666666666667

ttottott is a substring of S, and its filling rate is \displaystyle\frac{6-2}{8-2} = \frac{2}{3}.

There is no substring with a filling rate greater than \frac{2}{3}, so the answer is \frac{2}{3}.

Sample Input 3

coffeecup

Sample Output 3

0.00000000000000000

ff is a substring of S, and its filling rate is 0.

There is no substring with a filling rate greater than 0, so the answer is 0.

Problem Statement

Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.

He was typing while looking only at the keyboard, not the screen.

Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.

He did not mistakenly press any keys other than those for lowercase English letters.

The characters in T that were not mistakenly typed are called correctly typed characters.

Determine the positions in T of the correctly typed characters.

Constraints

• S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
• T is a string obtained by the procedure described in the problem statement.

Sample Input 1

abc
axbxyc

Sample Output 1

1 3 6

The sequence of Takahashi's typing is as follows:

• Type a.
• Try to type b but mistakenly type x.
• Press the backspace key, but the character is not deleted.
• Type b.
• Try to type c but mistakenly type x.
• Press the backspace key, but the character is not deleted.
• Try to type c but mistakenly type y.
• Press the backspace key, but the character is not deleted.
• Type c.

The correctly typed characters are the first, third, and sixth characters.

Sample Input 2

aaaa
bbbbaaaa

Sample Output 2

5 6 7 8

Sample Input 3

atcoder
atcoder

Sample Output 3

1 2 3 4 5 6 7

Takahashi did not mistakenly type any characters.

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