Problem Statement

Nathan O. Davis has been running an electronic bulletin board system named JAG-channel. He is now having hard time to add a new feature there --- threaded view.

Like many other bulletin board systems, JAG-channel is thread-based. Here a thread (also called a topic) refers to a single conversation with a collection of posts. Each post can be an opening post, which initiates a new thread, or a reply to a previous post in an existing thread.

Threaded view is a tree-like view that reflects the logical reply structure among the posts: each post forms a node of the tree and contains its replies as its subnodes in the chronological order (i.e. older replies precede newer ones). Note that a post along with its direct and indirect replies forms a subtree as a whole.

Let us take an example. Suppose: a user made an opening post with a message hoge; another user replied to it with fuga; yet another user also replied to the opening post with piyo; someone else replied to the second post (i.e. fuga”) with foobar; and the fifth user replied to the same post with jagjag. The tree of this thread would look like:

hoge
├─fuga
│　├─foobar
│　└─jagjag
└─piyo

For easier implementation, Nathan is thinking of a simpler format: the depth of each post from the opening post is represented by dots. Each reply gets one more dot than its parent post. The tree of the above thread would then look like:

hoge
.fuga
..foobar
..jagjag
.piyo

Your task in this problem is to help Nathan by writing a program that prints a tree in the Nathan's format for the given posts in a single thread.

Input

Input contains a single dataset in the following format:

n
k_1
M_1
k_2
M_2
:
:
k_n
M_n

The first line contains an integer n (1 \leq n \leq 1,000), which is the number of posts in the thread. Then 2n lines follow. Each post is represented by two lines: the first line contains an integer k_i (k_1 = 0, 1 \leq k_i < i for 2 \leq i \leq n) and indicates the i-th post is a reply to the k_i-th post; the second line contains a string M_i and represents the message of the i-th post. k_1 is always 0, which means the first post is not replying to any other post, i.e. it is an opening post.

Each message contains 1 to 50 characters, consisting of uppercase, lowercase, and numeric letters.

Output

Print the given n messages as specified in the problem statement.

Sample Input 1

1
0
icpc

Output for the Sample Input 1

icpc

Sample Input 2

5
0
hoge
1
fuga
1
piyo
2
foobar
2
jagjag

Output for the Sample Input 2

hoge
.fuga
..foobar
..jagjag
.piyo

Sample Input 3

8
0
jagjag
1
hogehoge
1
buhihi
2
fugafuga
4
ponyoponyo
5
evaeva
4
nowawa
5
pokemon

Output for the Sample Input 3

jagjag
.hogehoge
..fugafuga
...ponyoponyo
....evaeva
....pokemon
...nowawa
.buhihi

Sample Input 4

6
0
nakachan
1
fan
2
yamemasu
3
nennryou2
4
dannyaku4
5
kouzai11

Output for the Sample Input 4

nakachan
.fan
..yamemasu
...nennryou2
....dannyaku4
.....kouzai11

Sample Input 5

34
0
LoveLive
1
honoka
2
borarara
2
sunohare
2
mogyu
1
eri
6
kasikoi
7
kawaii
8
eriichika
1
kotori
10
WR
10
haetekurukotori
10
ichigo
1
umi
14
love
15
arrow
16
shoot
1
rin
18
nyanyanya
1
maki
20
6th
20
star
22
nishikino
1
nozomi
24
spiritual
25
power
1
hanayo
27
darekatasukete
28
chottomattete
1
niko
30
natsuiro
30
nikkonikkoni
30
sekaino
33
YAZAWA

Output for the Sample Input 5

LoveLive
.honoka
..borarara
..sunohare
..mogyu
.eri
..kasikoi
...kawaii
....eriichika
.kotori
..WR
..haetekurukotori
..ichigo
.umi
..love
...arrow
....shoot
.rin
..nyanyanya
.maki
..6th
..star
...nishikino
.nozomi
..spiritual
...power
.hanayo
..darekatasukete
...chottomattete
.niko
..natsuiro
..nikkonikkoni
..sekaino
...YAZAWA

Sample Input 6

6
0
2ch
1
1ostu
1
2get
1
1otsu
1
1ostu
3
pgr

Output for the Sample Input 6

2ch
.1ostu
.2get
..pgr
.1otsu
.1ostu

Problem Statement

Nathan O. Davis is running a company. His company owns a web service which has a lot of users. So his office is full of servers, routers and messy LAN cables.

He is now very puzzling over the messy cables, because they are causing many kinds of problems. For example, staff working at the company often trip over a cable. No damage if the cable is disconnected. It’s just lucky. Computers may fall down and get broken if the cable is connected. He is about to introduce a new computer and a new cable. He wants to minimize staff’s steps over the new cable.

His office is laid-out in a two-dimensional grid with H \times W cells. The new cable should weave along edges of the cells. Each end of the cable is at a corner of a cell. The grid is expressed in zero-origin coordinates, where the upper left corner is (0, 0).

Each staff starts his/her work from inside a certain cell and walks in the office along the grid in a fixed repeated pattern every day. A walking pattern is described by a string of four characters U, D, L and R. U means moving up, D means moving down, R means moving to the right, and L means moving to the left. For example, UULLDDRR means moving up, up, left, left, down, down, right and right in order. The staff repeats the pattern fixed T times. Note that the staff stays in the cell if the staff is going out of the grid through the wall.

You have the moving patterns of all staff and the positions of both ends of the new cable. Your job is to find an optimal placement of the new cable, which minimizes the total number his staff would step over the cable.

Input

The first line of the input contains three integers which represent the dimension of the office W, H (1 \leq W, H \leq 500), and the number of staff N (1 \leq N \leq 1000), respectively. The next line contains two x-y pairs (0 \leq x \leq W, 0 \leq y \leq H), which mean the position of two endpoints of a LAN cable to be connected. These values represents the coordinates of the cells to which the cable is plugged in its top-left corner. Exceptionally, x = W means the right edge of the rightmost cell, and y = H means the bottom edge of the bottommost cell.

Following lines describe staff’s initial positions and their moving patterns. The first line includes an x-y pair (0 \leq x \lt W, 0 \leq y \lt H), which represents the coordinate of a staff's initial cell. The next line has an integer T (1 \leq T \leq 100) and a string which consists of U, D, L and R, whose meaning is described as above. The length of a pattern string is greater than or equal to 1, and no more than 1,000. These two lines are repeated N times.

Output

Output the minimum number of times his staff step over the cable in a single line.

Sample Input 1

3 3 1
1 1 3 3
0 0
1 RRDDLLUU

Output for the Sample Input 1

1

Sample Input 2

3 3 1
0 0 3 3
0 0
1 RRDDLLUU

Output for the Sample Input 2

0

Sample Input 3

3 3 1
1 1 3 3
0 0
10 RRDDLLUU

Output for the Sample Input 3

10

Sample Input 4

3 3 4
1 1 3 3
0 0
10 R
2 0
10 D
2 2
10 L
0 2
10 U

Output for the Sample Input 4

1

Problem Statement

Ievan Ritola is a researcher of behavioral ecology. Her group visited a forest to analyze an ecological system of some kinds of foxes.

The forest can be expressed as a two-dimensional plane. With her previous research, foxes in the forest are known to live at lattice points. Here, lattice points are the points whose x and y coordinates are both integers. Two or more foxes might live at the same point.

To observe the biology of these foxes, they decided to put a pair of sensors in the forest. The sensors can be put at lattice points. Then, they will be able to observe all foxes inside the bounding rectangle (including the boundary) where the sensors are catty-corner to each other. The sensors cannot be placed at the points that have the same x or y coordinate; in other words the rectangle must have non-zero area.

The more foxes can be observed, the more data can be collected; on the other hand, monitoring a large area consumes a large amount of energy. So they want to minimize maximize the value given by N' / (|x_1 - x_2| \times |y_1 - y_2|), where N' is the number of foxes observed and (x_1, y_1) and (x_2, y_2) are the positions of the two sensors.

Let's help her observe cute foxes!

Input

The input is formatted as follows.

N
x_1 y_1 w_1
x_2 y_2 w_2
:
:
x_N y_N w_N

The first line contains a single integer N (1 \leq N \leq 10^5) indicating the number of the fox lairs in the forest. Each of the next N lines contains three integers x_i, y_i (|x_i|,\, |y_i| \leq 10^9) and w_i (1 \leq w_i \leq 10^4), which represent there are w_i foxes at the point (x_i, y_i). It is guaranteed that all points are mutually different.

Output

Output the minimized maximized value as a fraction:

a / b

where a and b are integers representing the numerator and the denominato respectively. There should be exactly one space before and after the slash. The fraction should be written in the simplest form, that is, a and b must not have a common integer divisor greater than one.

If the value becomes an integer, print a fraction with the denominator of one (e.g. 5 / 1 to represent 5). This implies zero should be printed as 0 / 1 (without quotes).

Sample Input 1

2
1 1 2
2 2 3

Output for the Sample Input 1

5 / 1

Problem Statement

Ayimok is a wizard.

His daily task is to arrange magical tiles in a line, and then cast a magic spell.

Magical tiles and their arrangement follow the rules below:

• Each magical tile has the shape of a trapezoid with a height of 1.

• Some magical tiles may overlap with other magical tiles.

• Magical tiles are arranged on the 2D coordinate system.

• Magical tiles' upper edge lay on a horizontal line, where its y coordinate is 1.

• Magical tiles' lower edge lay on a horizontal line, where its y coordinate is 0.

He has to remove these magical tiles away after he finishes casting a magic spell. One day, he found that removing a number of magical tiles is so tiresome, so he decided to simplify its process.

Now, he has learned "Magnetization Spell" to remove magical tiles efficiently. The spell removes a set of magical tiles at once. Any pair of two magical tiles in the set must overlap with each other.

For example, in Fig. 1, he can cast Magnetization Spell on all of three magical tiles to remove them away at once, since they all overlap with each other. (Note that the heights of magical tiles are intentionally changed for easier understandings.)

Fig. 1: Set of magical tiles which can be removed at once

However, in Fig. 2, he can not cast Magnetization Spell on all of three magical tiles at once, since tile 1 and tile 3 are not overlapped.

Fig. 2: Set of magical tiles which can NOT be removed at once

He wants to remove all the magical tiles with the minimum number of Magnetization Spells, because casting the spell requires magic power exhaustively.

Let’s consider Fig. 3 case. He can remove all of magical tiles by casting Magnetization Spell three times; first spell for tile 1 and 2, second spell for tile 3 and 4, and third spell for tile 5 and 6.

Fig. 3: One way to remove all magical tiles (NOT the minimum number of spells casted)

Actually, he can remove all of the magical tiles with casting Magnetization Spell just twice; first spell for tile 1, 2 and 3, second spell for tile 4, 5 and 6. And it is the minimum number of required spells for removing all magical tiles.

Fig. 4: The optimal way to remove all magical tiles(the minimum number of spells casted)

Given a set of magical tiles, your task is to create a program which outputs the minimum number of casting Magnetization Spell to remove all of these magical tiles away.

There might be a magical tile which does not overlap with other tiles, however, he still needs to cast Magnetization Spell to remove it.

Input

Input follows the following format:

N
xLower_{11} xLower_{12} xUpper_{11} xUpper_{12}
xLower_{21} xLower_{22} xUpper_{21} xUpper_{22}
xLower_{31} xLower_{32} xUpper_{31} xUpper_{32}
:
:
xLower_{N1} xLower_{N2} xUpper_{N1} xUpper_{N2}

The first line contains an integer N, which means the number of magical tiles.

Then, N lines which contain the information of magical tiles follow.

The (i+1)-th line includes four integers xLower_{i1}, xLower_{i2}, xUpper_{i1}, and xUpper_{i2}, which means i-th magical tile's corner points are located at (xLower_{i1}, 0), (xLower_{i2}, 0), (xUpper_{i1}, 1), (xUpper_{i2}, 1).

You can assume that no two magical tiles will share their corner points. That is, all xLower_{ij} are distinct, and all xUpper_{ij} are also distinct. The input follows the following constraints:

• 1 \leq N \leq 10^5

• 1 \leq xLower_{i1} < xLower_{i2} \leq 10^9

• 1 \leq xUpper_{i1} < xUpper_{i2} \leq 10^9

• All xLower_{ij} are distinct.

• All xUpper_{ij} are distinct.

Output

Your program must output the required minimum number of casting Magnetization Spell to remove all the magical tiles.

Sample Input 1

3
26 29 9 12
6 10 15 16
8 17 18 19

Output for the Sample Input 1

1

Sample Input 2

3
2 10 1 11
5 18 9 16
12 19 15 20

Output for the Sample Input 2

2

Sample Input 3

6
2 8 1 14
6 16 3 10
3 20 11 13
17 28 18 21
22 29 25 31
23 24 33 34

Output for the Sample Input 3

2

Problem Statement

Fox Ciel is developing an artificial intelligence (AI) for a game. This game is described as a game tree T with n vertices. Each node in the game has an evaluation value which shows how good a situation is. This value is the same as maximum value of child nodes’ values multiplied by -1. Values on leaf nodes are evaluated with Ciel’s special function -- which is a bit heavy. So, she will use alpha-beta pruning for getting root node’s evaluation value to decrease the number of leaf nodes to be calculated.

By the way, changing evaluation order of child nodes affects the number of calculation on the leaf nodes. Therefore, Ciel wants to know the minimum and maximum number of times to calculate in leaf nodes when she could evaluate child node in arbitrary order. She asked you to calculate minimum evaluation number of times and maximum evaluation number of times in leaf nodes.

Added pseudocode.(13:17 JST)
Ciel uses following algotithm:

function negamax(node, α, β)
    if node is a terminal node
        return value of leaf node
    else
        foreach child of node
            val := -negamax(child, -β, -α)
            if val >= β
                return val
            if val > α
                α := val
        return α

[NOTE] negamax algorithm

Input

Input follows following format:

n
p_1 p_2 ... p_n
k_1 t_{11} t_{12} ... t_{1k}
:
:
k_n t_{n1} t_{n2} ... t_{nk}

The first line contains an integer n, which means the number of vertices in game tree T.
The second line contains n integers p_i, which means the evaluation value of vertex i.
Then, next n lines which contain the information of game tree T.
k_i is the number of child nodes of vertex i, and t_{ij} is the indices of the child node of vertex i.
Input follows following constraints:

• 2 \leq n \leq 100

• -10,000 \leq p_i \leq 10,000

• 0 \leq k_i \leq 5

• 2 \leq t_{ij} \leq n

• Index of root node is 1.

• Evaluation value except leaf node is always 0. This does not mean the evaluation values of non-leaf nodes are 0. You have to calculate them if necessary.

• Leaf node sometimes have evaluation value of 0.

• Game tree T is tree structure.

Output

Print the minimum evaluation number of times and the maximum evaluation number of times in leaf node.
Please separated by whitespace between minimum and maximum.

minimum maximum

Sample Input 1

3
0 1 1
2 2 3
0
0

Output for the Sample Input 1

2 2

Sample Input 2

8
0 0 100 100 0 -100 -100 -100
2 2 5
2 3 4
0
0
3 6 7 8
0
0
0

Output for the Sample Input 2

3 5

Sample Input 3

8
0 0 100 100 0 100 100 100
2 2 5
2 3 4
0
0
3 6 7 8
0
0
0

Output for the Sample Input 3

3 4

Sample Input 4

19
0 100 0 100 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10
2 2 3
0
2 4 5
0
3 6 7 8
3 9 10 11
3 12 13 14
3 15 16 17
2 18 19
0
0
0
0
0
0
0
0
0
0

Output for the Sample Input 4

7 12

Problem Statement

You and your grandma are playing with graph automata, which is generalization of cell automata.

A graph automaton is expressed by a graph. The vertices of the graph have a time-dependent value, which can be either 0 or 1. There is no more than one edge between any of two vertices, but self-loops might exist.

The values of vertices change regularly according to the following rule: At time t+1, the value of vertex i will be 1 if and only if there are an odd number of edges from the vertex i to a vertex which has the value 1 at time t; otherwise 0.

Now, your forgetful grandma forgot the past states of the automaton. Your task is to write a program which recovers the past states from the current time and states --- time machines are way too expensive. There may be multiple candidates or no consistent states. For such cases, you must print an appropriate error message.

Input

The input is formatted as follows:

N
a_{11} ... a_{1N}
:
:
a_{N1} ... a_{NN}
v_1
:
:
v_N
T

The first line contains one integer N (2 \leq N \leq 300). N indicates the number of vertices. The following N lines indicate the adjacent matrix of the graph. When (i,j)-element is 1, there is an edge from vertex i to vertex j. Otherwise, there is no edge. The following N lines indicate the value vector of the vertices. The i-th element indicates the value of vertex i at time 0. Each element of the matrix and the vector can be 0 or 1. The last line contains one integer T (1 \leq T \leq 100,000,000). -T is the time your grandma wants to know the status at.

Output

Print the value vector at time -T separated one white space in one line as follows:

v_1 ... v_N

Each value must be separated with one white space. If there is no consistent value vectors, you should print none in one line. Or if there are multiple candidates and the solution is not unique (i.e. the solution is not unique), you should print ambiguous in one line.

Sample Input 1

2
1 1
0 1
1
1
1

Output for the Sample Input 1

0 1

Sample Input 2

2
0 1
0 0
1
0
1

Output for the Sample Input 2

ambiguous

Sample Input 3

2
0 1
0 0
1
0
2

Output for the Sample Input 3

none

Problem Statement

Ciel, an idol whose appearance and behavior are similar to a fox, is participating in a rehearsal for the live concert which takes place in a few days. To become a top idol, a large amount of effort is required!

The live stage can be expressed as a two-dimensional surface. The live stage has N spotlights to illuminate the stage. The i-th spotlight casts a light in the range of a circle with radius r_{i}. The center of the light cast by the i-th spotlight moves along an orbital path R_{i}. R_{i} is described as a closed polygon, though R_{i} might contain self-intersections. The spotlight begins to move from the first vertex of R_{i}. All of the orbital period of each spotlight are the same. Each spotlight moves at a constant speed, and all of them return to the starting point at the same time.

In the rehearsal, Ciel has to move from the starting point to the ending point indicated on the live stage. To achieve her goal, it is not allowed to fall out from the area illuminated with the spotlight. But, she doesn't have to be illuminated with the spotlight as long as she is standing on the starting point. You may assume that she can move fast enough. Answer if it is possible for her to move to the ending point.

Input

Each input dataset is given in the following format:

N sx sy ex ey
r_{1} K_{1} x_{11} y_{11} x_{12} y_{12} ... x_{1K_{1}} y_{1K_{1}}
r_{2} K_{2} x_{21} y_{21} x_{22} y_{22} ... x_{2K_{2}} y_{2K_{2}}
:
:
r_{N} K_{N} x_{N1} y_{N1} x_{N2} y_{N2} ... x_{NK_{N}} y_{NK_{N}}

All inputs are integer. All coordinate information satisfies -10,000 \leq x, y \leq 10,000. N (1 \leq N \leq 100) indicates the number of spotlights. (sx, sy) and (ex, ey) indicate the starting point and the ending point of Ciel’s path, respectively. The following N lines denote the information of each spotlight. r_{i} (1 \leq r_{i} \leq 100) indicates the radius of the spotlight. K_{i} (2 \leq K_{i} \leq 10) indicates the number of vertices in the orbital path. Then, K_{i} vertices are given. Two consecutive vertices on the same orbital path are located at different places. The spotlight moves from the first point (x_{i1}, y_{i1}) to the second point (x_{i2}, y_{i2}), then moves to the third point (x_{i3}, y_{i3}), and so on. After moving to the K_{i}-th point (x_{iK_{i}}, y_{iK_{i}}), the spotlight returns to the first point (x_{i1}, y_{i1}) and repeats again its movement.

Let d_{ij} be the closest distance between two central points of spotlight i and spotlight j. d_{ij} satisfies either of the following:

• d_{ij} > r_{i} + r_{j} + 0.000001

• d_{ij} < r_{i} + r_{j} - 0.000001

Furthermore, let d_{i} be the closest distance between a central point of spotlight i and either the starting point or the ending point. d_{i} satisfies either of the following:

• d_{i} > r_{i} + 0.000001

• d_{i} < r_{i} - 0.000001

Output

If it is possible for Ciel to move the ending point without falling out from the illuminated area, output Yes in one line. Otherwise, output No.

Sample Input 1

2 1 1 9 -1
2 2 1 1 -9 1
1 2 -1 -1 9 -1

Output for the Sample Input 1

Yes

Sample Input 2

2 1 1 9 -1
2 2 1 1 -9 1
1 2 9 -1 -1 -1

Output for the Sample Input 2

No

Sample Input 3

2 11 6 -9 1
6 4 10 5 10 0 5 0 5 5
5 4 -10 0 -10 5 -5 5 -5 0

Output for the Sample Input 3

Yes

Sample Input 4

1 1 9999 -1 0
100 2 0 0 0 10000

Output for the Sample Input 4

Yes

Problem Statement

You are practicing a juggle that involves in a number of square tiles. They all look the same in their size, but actually there are three different kinds of the tiles, A, B and X. The kind of a tile can be distinguishable by its mass. All the tiles of the same kind have exactly the same mass. The mass of type A tiles is within the range [mA1, mA2]. The mass of type B tiles is similarly within the range [mB1, mB2]. You don’t know the exact numbers for type A and B. The mass of type X tiles is exactly mX.

You have just got one big object consists of the tiles. The tiles are arranged in an H \times W grid. All the adjacent tiles are glued together on the edges. Some cells in the H \times W grid can be empty.

You wanted to balance the object on a pole. You started to wonder the center of gravity of the object, then. You cannot put the object on a pole if the center of gravity is on an empty cell. The center of gravity of each single square tile is at the center of the square. The center of gravity of an object which combines two objects with masses m_{1} and m_{2} is the point dividing the line segment between those centers in the ratio m_{2} : m_{1} internally.

Your task is to write a program that computes the probability that the center of gravity of the big object is actually on the object, not on a hole in the object. Although the exact mass is unknown for tile A and B, the probability follows the continuous uniform distribution within the range mentioned above. You can assume the distribution is independent between A and B.

Input

The input is formatted as follows.

H W
mA1 mA2 mB1 mB2 mX
M_{1,1}M_{1,2}...M_{1,W}
M_{2,1}M_{2,2}...M_{2,W}
:
:
M_{H,1}M_{H,2}...M_{H,W}

The first line of the input contains two integers H and W (1 \leq H, W \leq 50) separated by a space, where H and W are the numbers of rows and columns of given matrix.

The second line of the input contains five integers mA1, mA2, mB1, mB2 and mX (1 \leq mA1 \lt mA2 \leq 100, 1 \leq mB1 \lt mB2 \leq 100 and 1 \leq mX \leq 100) separated by a space.

The following H lines, each consisting of W characters, denote given matrix. In those H lines, A, B and X denote a piece of type A, type B and type X respectively, and . denotes empty cell to place no piece. There are no other characters in those H lines.

Of the cell at i-th row in j-th column, the coordinate of the left top corner is (i, j), and the coordinate of the right bottom corner is (i+1, j+1).

You may assume that given matrix has at least one A, B and X each and all pieces are connected on at least one edge. Also, you may assume that the probability that the x-coordinate of the center of gravity of the object is an integer is equal to zero and the probability that the y-coordinate of the center of gravity of the object is an integer is equal to zero.

Output

Print the probability that the center of gravity of the object is on the object. The output should not contain an error greater than 10^{-8}.

Sample Input 1

3 3
2 4 1 2 1
XAX
B.B
XAX

Output for the Sample Input 1

0.0000000000000

Sample Input 2

4 2
1 100 1 100 50
AX
XB
BA
XB

Output for the Sample Input 2

1.0

Sample Input 3

2 3
1 2 3 4 2
X.B
AXX

Output for the Sample Input 3

0.500

Sample Input 4

10 10
1 100 1 100 1
AXXXXXXXXX
X........X
X........X
X..XXXXXXX
X........X
XXXXXX...X
X........X
X......X.X
X......X.X
XXXXXXXXXB

Output for the Sample Input 4

0.4930639462354

Sample Input 5

25 38
42 99 40 89 3
...........X...............X..........
...........XXX..........XXXX..........
...........XXXXX.......XXXX...........
............XXXXXXXXXXXXXXX...........
............XXXXXXXXXXXXXXX...........
............XXXXXXXXXXXXXX............
.............XXXXXXXXXXXXX............
............XXXXXXXXXXXXXXX...........
...........XXXXXXXXXXXXXXXXX..........
.......X...XXXXXXXXXXXXXXXXX...X......
.......XX.XXXXXXXXXXXXXXXXXX..XX......
........XXXXXXXXXXXXXXXXXXXX.XX.......
..........XXXXXXXXXXXXXXXXXXXX........
.........XXXXX..XXXXXXXX..XXXXX.......
.......XXXXXX....XXXXX....XXXXXX......
......XXXXXXXX...XXXXX..XXXXXXXX.X....
....XXXXXXX..X...XXXXX..X..XXXXXXXX...
..BBBXXXXXX.....XXXXXXX......XXXAAAA..
...BBBXXXX......XXXXXXX........AAA....
..BBBB.........XXXXXXXXX........AAA...
...............XXXXXXXXX..............
..............XXXXXXXXXX..............
..............XXXXXXXXXX..............
...............XXXXXXXX...............
...............XXXXXXXX...............

Output for the Sample Input 5

0.9418222212582

Problem Statement

You are a programmer who loves pretty girl games (a sub-genre of dating simulation games). A game, which is titled "Floatable Heart" and was released last Friday, has arrived at your home just now. This game has multiple stories. When you complete all of those stories, you can get a special figure of the main heroine, Megumi. So, you want to hurry to play the game! But, let's calm down a bit and think how to complete all of the stories in the shortest time first.

In fact, you have the special skill that allows you to know the structure of branching points of games. By using the skill, you have found out that there are n branching points in this game and i-th branching point has k_{i} choices. This game is so complicated that multiple routes get to i-th branching point probably. You also noticed that it takes c_{ij} minutes to proceed from i-th branching point to another branching point (or an ending), if you select j-th choice of i-th branching point. Of course you need to select all the choices on all the branching points and read stories between a branching point and another branching point (or an ending) to complete all of those stories. In addition, you can assume it only takes negligible time to return to the beginning of the game ("reset") and to play from the beginning to the first branching point.

The game’s manual says that this game has an additional feature called "Quick Save”, and the feature allows you to record the point where you are currently playing and return there at any time later. However, this feature is not working for some bug. Thus you have to restart from the first branching point every time, if you reach an ending or quit the game on the way. Any patch to fix this bug has not been yet published. This is an imposed tribulation for the fastest players.

Well, let's estimate how long it will take for completing all of the stories in the shortest time.

Input

A data set is given in the following format.

n
k_{1} t_{11} c_{12} ... t_{1k_{1}} c_{1k_{1}}
:
:
k_{n} t_{n1} c_{n2} ... t_{nk_{n}} c_{nk_{n}}

The first line of the data set contains one integer n (2 \leq n \leq 1{,}000), which denotes the number of the branching points in this game. The following n lines describe the branching points. The i-th line describes the branching point of ID number i. The first integer k_{i} (0 \leq k_{i} \leq 50) is the number of choices at the i-th branching point. k_{i} ≥0 means that the i-th branching point is an ending. Next 2k_{i} integers t_{ij} (1 \leq t_{ij} \leq n) and c_{ij} (0 \leq c_{i}j \leq 300) are the information of choices. t_{ij} denotes the ID numbers of the next branching points when you select the j-th choice. c_{ij} denotes the time to read the story between the i-th branching point and the t_{ij}-th branching point. The branching point with ID 1 is the first branching point. You may assume all the branching point and endings are reachable from the first branching point. You may also assume that there is no loop in the game, that is, no branching point can be reached more than once without a reset.

Output

Print the shortest time in a line.

Sample Input 1

2
1 2 2
0

Output for the Sample Input 1

2

Sample Input 2

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

Output for the Sample Input 2

24

Sample Input 3

6
3 2 100 3 10 3 10
1 4 100
1 4 10
3 5 1 5 1 6 1
0
0

Output for the Sample Input 3

243

Problem Statement

You have a board with height two and width W. The board is divided into 1x1 cells. Each row of the board is numbered 1 and 2 from top to bottom and each column is numbered 1 to W from left to right. We denote a cell at the i-th row in the j-th column by (i, j). Initially, some checkers are placed on some cells of the board. Here we assume that each checker looks the same. So we do not distinguish each checker. You are allowed to perform the following operations on the board:

1. Square rotation: Choose a 2x2 square on the board. Then move checkers in the 2x2 square such that the checkers rotate their position in the square by 90 degrees in either clockwise or counterclockwise direction.
   
2. Triangular rotation: Choose a set of cells on the board that form a triangle. Here, we call a set of cells triangle if it is formed by removing exactly one cell from a 2x2 square. In the similar manner with the square rotation, rotate checkers in the chosen triangle in either clockwise or counterclockwise direction.
   

The objective in this problem is to transform the arrangement of the checkers into desired arrangement by performing a sequence of rotation operations. The information of the initial arrangement and the target arrangement are given as the input. For the desired arrangement, one of the following is specified for each cell (i, j): i. cell (i,j) must contain a checker, ii. cell (i,j) must not contain a checker, or iii. there is no constraint for cell (i, j). Compute the minimum required number of operations to move the checkers so the arrangement satisfies the constraints and output it.

Input

The input is formatted as follows.

W
s_{11}s_{11}...s_{1W}
s_{21}s_{21}...s_{2W}

t_{11}t_{11}...t_{1W}
t_{21}t_{21}...t_{2W}

The first line of the input contains an integer W (2 \leq W \leq 2,000), the width of the board. The following two lines contain the information of the initial arrangement. If a cell (i, j) contains a checker in the initial arrangement, s_{ij} is o. Otherwise, s_{ij} is .. Then an empty line follows. The following two lines contain the information of the desired arrangement. Similarly, if a cell (i, j) must contain a checker at last, t_{ij} is o. If a cell (i, j) must not contain a checker at last, t_{ij} is .. If there is no condition for a cell (i, j), t_{ij} is *. You may assume that a solution always exists.

Output

Output the minimum required number of operations in one line.

Sample Input 1

3
.oo
o..

o.o
o..

Output for the Sample Input 1

1

Sample Input 2

5
.o.o.
o.o.o

o.o.o
.o.o.

Output for the Sample Input 2

3

Sample Input 3

4
o.o.
o.o.

.*.o
.o.*

Output for the Sample Input 3

4

Sample Input 4

20
oooo.....ooo......oo
.o..o....o..oooo...o

...o*.o.oo..*o*.*o..
.*.o.o.*o*o*..*.o...

Output for the Sample Input 4

25

Sample Input 5

30
...o...oo.o..o...o.o........o.
.o.oo..o.oo...o.....o........o

**o.*....*...*.**...**....o...
**..o...*...**..o..o.*........

Output for the Sample Input 5

32