Problem Statement

Kyoto University offers N lectures and you need more than or equal to K credits to advance to the next grade. You can earn a_i credits by taking i-th lecture. You want to take as small number of lectures as possible to advance to the next grade. How many lectures do you need to take?

Constraints

• 1 \leq N \leq 50
• 1 \leq K \leq 1,000
• 1 \leq a_i \leq 20
• N, K, a_i are integers.

Sample Input 1

5 15
3 8 2 5 6

Sample Output 1

3

For example, you can adcance to the next grade with first, second, and fourth lectures.

Sample Input 2

5 25
3 8 2 5 6

Sample Output 2

-1

You can not advance to the next grade even by taking all the lectures.

Sample Input 3

4 20
1 1 20 19

Sample Output 3

1

Problem Statement

There is a huge kusunoki (camphor tree) in front of the clock tower of Kyoto University. It is reported that this kusunoki has the following structure.

• There exists a positive integer N and the kusunoki has 2^N-1 branch points, which are numbered from 1 to 2^N-1.
• For each integer i that holds 1 \leq i \leq 2^{N-1}-1, the kusunoki has branches according to the following rules.
  • Branch point i and 2i are connected with a branch.
  • Branch point i and 2i + 1 are connected with a branch.
• There is no branch that does not hold the above rules.

For example, for N=3, the structure of the kusunoki is as follows.

Kusunoki N=3

You want to climb this kusunoki. You can climb from branch point S to T if and only if S=T or there exists a path of branches from S to T, where the numbers of branch points are in ascending order from S to T. Given two integers S and T, determine whether you can climb from branch point S to T. Also, if it is possible, answer the lowerst number of branches you need to climb.

Constraints

• 1 \leq N \leq 25
• 1 \leq S \leq 2^N-1
• 1 \leq T \leq 2^N-1
• N,S,T are integers.

Sample Input 1

3 2 4

Sample Output 1

1

Since you can climb from branch point 2 to 4 through one branch, print 1.

Sample Input 2

3 7 1

Sample Output 2

-1

Sample Input 3

4 2 2

Sample Output 3

0

Problem Statement

One of the buildings in Kyoto University requires a password to enter.

This password consists of lowercase alphabets and you, one of those who use the building, know the password.

The authentication system of the building calculates a hash value from the password that is entered, and checks whether the hash value matches.

The hash value of string S of length N is calculated based on the following formula.

A^1 \times C[S_1] + A^2 \times C[S_2] + ... + A^N \times C[S_N]

A is an integer more than or equal to 2 and less than or equal to 10, and C[a]=1, C[b]=2, ..., C[z]=26.

You are so busy that you want to pass the authentication with as short password as possible.

Find the shortest password, the hash value of which is the same as that of the original password. If multiple passwords of the minimum length exist, find the lexicographically maximum one.

Constraints

• 2 \leq A \leq 10
  • A is an integer.
• 1 \leq |S| \leq 1,000
  • S consists of lowercase alphabets.

Sample Input 1

2
kupc

Sample Output 1

yzp

The hash value of the original string is

2^1 \times 11 + 2^2 \times 21 + 2^3 \times 16 + 2^4 \times 3 = 282.

The hash value of the output is also

2^1 \times 25 + 2^2 \times 26 + 2^3 \times 16 = 282.

Sample Input 2

10
abcde

Sample Output 2

utuvc

Sample Input 3

4
zzz

Sample Output 3

zzz

Sample Input 4

9
kyotouniversityprogrammingcontest

Sample Output 4

txxsxtwztwyrrsyyzwxyrtuzuxsvvswzs

The hash value is very large in some cases.

Problem Statement

You want to write a positive integer less than or equal to 10^9 in each cell of a tile with N rows and N columns. The tile must hold the following condition after you have written all positive integers.

• For any 3 consecutive cells that are aligned vertically, horizonally, or diagonally, the cells must contain at least 2 different positive integers.

You want to make the maximum integer K in the tile as small as possible. Find the minimum K and the number of the distinct states of tiles where K is the minimum value, modulo 10^9 + 7.

Constraints

• N is an integer.
• 1 \leq N \leq 200

Sample Input 1

1

Sample Output 1

1 1

Since there are no 3 consecutive cells, you can fill every cell with 1 and the number of different states are 1.

Sample Input 2

2

Sample Output 2

1 1

Sample Input 3

4

Sample Output 3

2 18

Problem Statement

There are n treasure boxes and m keys.

The treasure boxes are numbered from 1 to n and treasure box i contains a jewel with value v_i.

The keys are numbered from 1 to m and key i can open either treasure box x_i or y_i. (You can not open both of the treasure boxes only using key i.)

You can only get 1 jewel in total even if you open the same treasure box several times.

Find the maximum sum of the value of the jewels you can obtain.

Constraints

• All input values are integers.
• 1 \leq n \leq 10^5
• 1 \leq m \leq 2 \times 10^5
• 1 \leq v_i \leq 10^{12} (1 \leq i \leq n)
• 1 \leq x_i, y_i \leq n (1 \leq i \leq m)

Sample Input 1

5 4
20 10 5 8 6
1 2
2 3
3 1
4 5

Sample Output 1

43

You can obtain the maximum total value of 43 as follows.

• Use key 1 for treasure box 1
• Use key 2 for treasure box 2
• Use key 3 for treasure box 3
• Use key 4 for treasure box 4

Sample Input 2

7 4
8 10 9 15 6 3 7
1 7
2 3
3 4
5 6

Sample Output 2

39

Sample Input 3

10 7
1 9 1 9 1 1 4 5 1 4
1 2
2 3
2 3
3 4
5 6
6 8
7 9

Sample Output 3

30

Sample Input 4

4 4
20 17 10 1
1 2
1 2
3 3
3 4

Sample Output 4

48

Multiple keys can open the same set of treasure boxes, and some keys can open only one kind of treasure box.

Sample Input 5

23 20
683654281944 786549938314 108776810532 691131809160 942432243130 63770179509 238399760640 777689878960 646058383313 576573571139 18835030915 479397445387 877859338277 965037937502 199599909896 785875134824 682649947008 167867064215 956377730283 681772713017 633843536114 123843426658 384215401230
4 10
17 19
9 19
20 9
12 19
10 18
13 21
23 19
7 21
11 15
16 19
15 8
8 2
19 10
22 21
14 23
3 19
1 12
6 9
2 10

Sample Output 5

11387100771264

Inputs or outputs may overflow 32-bit integers.

Problem Statement

A subsequence is a sequence that can be derived from another sequence by deleting some (incuding 0) elements without changing the order of the remaining elements. For example, (4, 2, 1), (7, 4, 3, 2, 1), and (empty) are subsequences of (7, 4, 3, 2, 1), but (1, 2) is not.

A sequence s of length n is called "575-sequence" if there exist numerical sequences a, b, and c that satisfy the following constraints.

• A sequence made by concatenating a, b, and c is a permutation of (1, 2, ..., n).
• min_i(a_i) < min_i(b_i) < min_i(c_i)
• Σs_{a_i} = 5
• Σs_{b_i} = 7
• Σs_{c_i} = 5

For example, ex=(ex_1, ex_2, ex_3, ex_4)=(5, 3, 5, 4) is a 575-sequence, but (5, 5, 7) is not. For ex, a=(1), b=(2, 4), and c=(3) satisfy the above constraints.

You are given a sequence x=(x_1, x_2, ..., x_N) of length N. Each term x_i satisfies 2 \leq x_i \leq 7. How many 575-sequences can you remove one by one from x?

Constraints

• 1 \leq N \leq 100
• 2 \leq x_i \leq 7
• N, x_i are integers

Sample Input 1

5
2 3 5 4 3

Sample Output 1

1

(2, 3, 5, 4, 3) is a 575-sequence. a=(1, 5), b=(2, 4), and c=(3) satisfy the constraints of 575-sequence.

Sample Input 2

10
5 6 2 3 5 5 5 7 5 3

Sample Output 2

2

Firstly, you can remove a 575-sequence (5, 2, 5, 5), which consists of the first, third, fifth, and sixth terms of x. For (5, 2, 5, 5), for example, a=(1), b=(2, 4), and c=(3) satisfy the constraints.

The remaining sequence, where the first, third, fifth, and sixth terms are removed from x is (6, 3, 5, 7, 5, 3). You can remove a 575-sequence (5, 7, 5), which consists of the third, fourth, and fifth terms of the remaining sequence.

Sample Input 3

5
6 6 6 6 6

Sample Output 3

0

Sample Input 4

9
5 3 2 2 7 3 5 4 3

Sample Output 4

2

Sample Input 5

8
5 5 4 3 5 5 4 3

Sample Output 5

2

Sample Input 6

22
2 3 4 5 6 7 6 5 4 3 2 2 3 4 5 6 7 6 5 4 3 2

Sample Output 6

3

Problem Statement

You are playing the following game.

1. You are given a tree with N = 100 vertices and M (= N-1 = 99) edges, and an integer X. The vertices of T are numbered from 1 to N. For each i (1 \leq i \leq M), vertex a_{i} and b_{i} are connected with an edge.
2. You make graph G by adding A (>= 0) edges to tree T one by one such that G does not have multiple edges and self-loops.
3. The edges in G which also exist in T disappear and G is renamed G' after the numbers of the vertices in G are permutated. G' has N = 100 vertices and A edges. The vertices in G' are numbered from 1 to N, and for each i (1 \leq i \leq A), c_{i} and d_{i} are connected with an edge.
4. The information on tree T, graph G, and integer X disappear from your memory.
5. You look at graph G' and declare an integer Y. If X = Y, you win.

You want to win the above game even if any tree T and integer X are given. Given tree T and integer X, find how to add A edges to T, and then given the generated G', find integer Y to win the game.

Constraints

• N = 100
• M = 99
• T is a tree.
• 1 \leq a_{i}, b_{i} \leq N (1 \leq i \leq M)
• 0 \leq X \leq 10^{18}
• 0 \leq A \leq {}_NC_2-M = 4,851
• 1 \leq c_{i}, d_{i} \leq N (1 \leq i \leq A)
• N, M, A, a_{i}, b_{i}, c_{i}, d_{i}, X are integers.

Input and Output

This problem has encode and decode phases, each of which is executed independently.

In encode phase, you take tree T and integer X, and find how to add edges to tree T. In decode phase, you take the generated graph G', and find integer Y.

Input (encode phase)

In encode phase, input is given from Standard Input in the following format:

String encode is given on the first line.

encode
N M
a_{1} b_{1}
a_{2} b_{2}
:
a_{M} b_{M}
X

Output (encode phase)

In encode phase, you must print A+1 lines.

Print A on the first line. Then, print the vertices of the i-th (1 \leq i \leq A) added edge on the following i-th line, a single space in between.

Input (decode phase)

In decode phase, input is given from Standard Input in the following format:

String decode is given on the first line.

decode
N A
c_{1} d_{1}
c_{2} d_{2}
:
c_{A} d_{A}

Output (decode phase)

Print Y. If X = Y, your output is correct.

Judge

The judging procedure is run in the following steps.

1. Two processes are launched to run the submitted program for the encode and decode phases.
2. The input for the encode phase is given to the process for encoding. Note that EOF is not given.
3. Wait until the process for encoding prints the output of the encode phase and the process for encoding exits completely.
4. If graph G, which is generated by the output of the encode phase, contains multiple edges and self-loops or the numbers of the vertices is not in the range: [1, N], the answer is wrong.
5. The output for the decode phase is given to the process for decoding. Note that EOF is not given.
6. Wait until the process for decoding prints the output of the decode phase and the process for decoding exits completely.
7. If X = Y, your program is correct, otherwise, wrong.

Note that if the formats of the outputs are invalid, the submitted program is also judged as wrong.

Sample Input 1 (encode phase)

encode
100 99
49 74
50 84
78 91
12 14
9 62
54 77
47 88
29 55
52 53
3 53
53 63
33 95
9 57
44 48
3 13
3 73
1 49
62 63
48 53
55 94
50 60
89 95
57 64
75 96
7 48
41 99
44 79
21 94
13 50
42 82
1 16
22 88
19 34
63 87
1 36
14 58
18 56
33 82
12 37
55 84
87 96
12 55
4 76
64 68
38 52
40 50
38 59
47 75
17 32
18 83
20 63
76 92
54 71
34 59
16 89
39 94
2 98
11 85
24 60
28 76
46 70
19 23
41 46
36 40
68 93
15 37
2 68
82 90
4 26
45 90
28 59
43 94
10 44
16 54
65 97
41 51
10 27
96 97
10 86
52 91
5 44
18 28
32 99
67 84
67 100
46 80
55 72
18 80
69 71
6 43
25 71
30 96
8 57
11 88
80 81
19 61
30 35
8 31
42 66
382174891210833608

Sample Output 1 (encode phase)

2
1 2
2 4

Sample Input 1 (decode phase)

decode
100 2
49 33
35 49

Note that the numbers of the vertices in G' may be different from the ones of T.

Sample Output 1 (decode phase)

382174891210833608

Problem Statement

You are compounding n kinds of liquid into a potion.

The volume of liquid i (1 \leq i \leq n) is v_i.

When you use i-th (1 \leq i \leq n) liquid of volume w_i (0 \leq w_i \leq v_i) for each i, you earn the effectiveness of $Σw_i \times h_i.

Note that each volume you use must be an integer.

You also have m conditions and i-th condition (1 \leq i \leq m) is as follows.

• If you use liquid a_i of volume more than or equal to x_i, you must also use liquid b_i of volume more than or equal to y_i.

Find the maximum effectiveness of the potion you can obtain within the above conditions.

Constraints

• All input values are integers.
• 1 \leq n \leq 1,000
• 1 \leq m \leq 2,000
• 1 \leq v_i \leq 10^6 (1 \leq i \leq n)
• -10^6 \leq h_i \leq 10^6 (1 \leq i \leq n)
• 1 \leq a_i, b_i \leq n (1 \leq i \leq m)
• 0 \leq x_i \leq v_{a_i} (1 \leq i \leq m)
• 0 \leq y_i \leq v_{b_i} (1 \leq i \leq m)
• The same condition is given at most once.

Sample Input 1

2 2
1000 1800
1 -10
1 200 2 10
1 801 2 1000

Sample Output 1

700

You can get the maximum effectiveness by using liquid 1 of volume 800 and liquid 2 of volume 10.

Sample Input 2

1 4
500
-3
1 0 1 100
1 50 1 300
1 300 1 400
1 401 1 410

Sample Output 2

-1200

You must use liquid 1 of volume at least 400.

Sample Input 3

6 4
100 30 40 50 60 70
3 -5 2 -1 20 -10
1 20 2 20
3 11 2 25
2 24 4 10
3 30 1 80

Sample Output 3

1445

Sample Input 4

1 1
1000000
1000000
1 0 1 0

Sample Output 4

1000000000000

Some answers overflow 32-bit integers.

Problem Statement

There are n magic stones aligned in a line from left to right.

At first, no magic stones are activated.

You use m kinds of magic. If you use magic i, all the l_i-th, l_i+1-th, ..., r_i-th magic stones from the left get activated. ( Magic stones which are already activated also keep activated. )

However, once all the x_1-th, x_2-th, ..., x_k-th magic stones are activated, no more magic stones get activated even if you use more magic.

You want to activate as many magic stones as possible by using each magic exactly once in any order you want.

Find the maximum number of magic stones you can activate.

Constraints

• All input values are integers.
• 1 \leq n \leq 10^5
• 1 \leq m \leq 10^5
• 1 \leq k \leq n
• 1 \leq l_i \leq r_i \leq n
• 1 \leq x_1 < x_2 < ... < x_k \leq n
• (l_i, r_i) (i=1,...,m) is distinct from each other.

Sample Input 1

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

Sample Output 1

7

You can activate all the magic stones by using magic in the following order.

• Use the second magic, and the third and fourth magic stones get activated.
• Use the first magic, and the first and second magic stones get activated.
• Use the third magic, and the fifth, sixth, and seventh magic stones get activated.

Sample Input 2

10 4 1
6
1 2
4 5
2 7
5 10

Sample Output 2

9

Sample Input 3

6 1 2
2 6
3 4

Sample Output 3

2

Problem Statement

There is a grid with H rows and W columns. Originally, each cell in the grid is painted white or black. The cell on the i-th row and j-th column is painted white if a_{i,j} is .. It is painted black if a_{i,j} is #. You want to paint some white cells red within the following constraints.

• Each row and column must have one or more red cells.
• When a graph is constructed as follows, the graph must be connected.
  • For all red cells, create the corresponding vertices. (The number of vertices in the graph is equal to the number of red cells in the grid. )
  • Add edges to all pairs of vertices, the corresponding cells of which are on the same row or column.

Find the minimum number of cells you need to paint red to sarisfy the above constraints. Also, find the number of such ways (where the number of red cells is minimum) module 10^9 + 7.

Constraints

• 1 \leq H \leq 10^4
• 1 \leq W \leq 50
• H, W are integers.
• a_{i,j} is either . or #.

Sample Input 1

2 3
...
.#.

Sample Output 1

4 4

There are 4 ways to paint the grid. (o represents a red cell. )

ooo  ooo  oo.  .oo
o#.  .#o  o#o  o#o

Sample Input 2

2 3
#..
.##

Sample Output 2

-1

There are no ways to satisfy the constraints.

Sample Input 3

3 10
...#...#..
#...#...#.
..##......

Sample Output 3

12 35640

Sample Input 4

6 6
......
......
......
......
......
......

Sample Output 4

11 60466176

Problem Statement

You have 3 integers n, m, and k. Count the number of numerical sequences of length n, which satisfy the following conditions, modulo 10^9 + 7.

1. s_i (1 \leq i \leq n) is an integer greather than or equal to 0, and less than or equal to m.
2. 0\ xor\ s_1\ xor\ s_2\ xor\ ...\ s_n = k. xor represents bitwise exclusive OR.

Constraints

• n, m, k are integers.
• 0 \leq n, m, k \leq 10^{18}

Sample Input 1

0 0 0

Sample Output 1

1

The number of numerical sequences with length 1 is 1. This sequence satisfies condition 2.

Sample Input 2

1 1 0

Sample Output 2

1

Sample Input 3

3 2 3

Sample Output 3

6

The following 6 sequences satisfy the constraints.

• { 0, 1, 2 }
• { 0, 2, 1 }
• { 1, 0, 2 }
• { 1, 2, 0 }
• { 2, 0, 1 }
• { 2, 1, 0 }

Sample Input 4

10 10 15

Sample Output 4

620478679

Problem Statement

There are a board with H rows and W columns. Each cell on the board is one of the following states: "one coin is placed face up", "one coin is placed face down", or "no coin is placed".

There are also W + H cards and one of the following is written on each card: "Row 1", "Row 2", ..., "Row H", "Column 1", "Column 2", ..., and "Column W". (Each type is written on exactly one card.)

Two players play a game using the board and cards. In this game, two players play their turns alternatingly.

In each turn, one of the players takes the following actions.

• The player removes 1 card he or she wants to.
• When a card is removed, all the coins on the row or column written on the card are turned over.
• The game ends when they have removed all cards or when all the coins are facing up.

When the game ends, the players earn scores according to the final state of the game as follows.

• The player who remove a card last earns 1 point.
• If all the coins are facing up, both players earn 2 points.

Find the total score of the first mover, assuming that both players play optimally to maximize their own scores.

Constraints

• 1 \leq W, H \leq 2,000
• m_{ij} is ., o, or x
• One or more coins are facing down

Partial Scores

30 points will be awarded for passing the test set satisfying the following:

• There are at least one coins facing down on each row.
• There are at least one coins facing up or down on each column.

Another 370 points will be awarded for passing the test set without addtional constraints and you can get 400 points in total.

Sample Input 1

2 5
.x.x.
x.o.x

Sample Output 1

3

This input satisfies the additional constraint.

Sample Input 2

7 2
x.
xx
x.
xx
x.
xx
x.

Sample Output 2

3

This input satisfies the additional constraint.

Sample Input 3

4 3
x.o
.x.
x.x
...

Sample Output 3

1

Sample Input 4

5 1
x
o
.
o
x

Sample Output 4

2

Sample Input 5

39 40
.........o..............................
.............................o..........
.................o......................
......o...............................x.
...x......o.............................
...........................o......o.....
.........................x..............
.................o.............o........
..................x.....................
.............o..........................
.......................................o
...............o........................
.....x.....o............................
..................o.....................
..o.........o...........................
...............x........................
.......o............................x...
........................x.....o.........
...................o.........o..........
........x..........................o....
......................o...o.............
..............o..................o......
..............x.........................
x.......................................
..o....................x................
.........................o..............
.o...................................o..
.................................o......
.o..................x...................
...........o....o.......................
.............x..........................
...............................x........
....o..............................o....
..........................o.x...........
...................x....................
.....................................o..
.........x..............................
o......................................o
.....................x..........o.......

Sample Output 5

3

Sample Input 6

38 39
.......o............................x..
.........x.............................
................x......................
............x..........................
.................x..........o..........
..................................o..o.
...............................o.......
.....................x..........o......
.............o.........................
..o....................o...............
....x..................................
...................o...................
..................o....................
.....x.....o...........................
.o..................o..................
....................o......x...........
.........................o.............
..................x....................
...............o.......................
......o...............................x
.......................o.........x.....
...............x.......................
.o.....................................
.........o.............................
o......................................
..............o.......o................
............o......o...................
........o..........................o...
..........................o.o..........
...x......o............................
......................x................
.............x.........................
o...o..................................
........o....................x.........
..............o........................
................o..............o.......
........................x.....o........
.........................x.............

Sample Output 6

2