Codeforces Round #369 (Div. 2) A~D

Codeforces Round #369 (Div. 2) A~D

A. Bus to Udayland

time limit per test

memory limit per test

input

output

ZS the Coder and Chris the Baboon are travelling to Udayland! To get there, they have to get on the special IOI bus. The IOI bus has nrows of seats. There are 4

ZS and Chris are good friends. They insist to get a pair of neighbouring empty seats. Two seats are considered neighbouring if they are in the same row and in the same pair. Given the configuration of the bus, can you help ZS and Chris determine where they should sit?

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 1000)

Then, n lines follow. Each line contains exactly 5

Each character, except the walkway, equals to 'O' or to 'X'. 'O' denotes an empty seat, 'X' denotes an occupied seat. See the sample cases for more details.

Output

If it is possible for Chris and ZS to sit at neighbouring empty seats, print "YES" (without quotes) in the first line. In the next n

If there is no pair of seats for Chris and ZS, print "NO" (without quotes) in a single line.

If there are multiple solutions, you may print any of them.

Examples

input

6OO|OXXO|XXOX|OOXX|OXOO|OOOO|XX

output

YES++|OXXO|XXOX|OOXX|OXOO|OOOO|XX

input

4XO|OXXO|XXOX|OXXX|OX

output

NO

input

5XX|XXXX|XXXO|OXXO|OOOX|XO

output

YESXX|XXXX|XXXO|OXXO|++OX|XO

Note

Note that the following is an incorrect configuration for the first sample case because the seats must be in the same pair.

O+|+X

XO|XX

OX|OO

XX|OX

OO|OO

OO|XX

题解：ZS和Chris坐bus去旅游，要上车啦。(滴滴。。学生卡。。）规定他们两个人一定要坐在一起。如果最先找出的pair座位就坐下，就输出YES并标志为++。否则输出NO。复杂度O(n)。水题。

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include #include #include #include #include #include #include

B. Chris and Magic Square

time limit per test

memory limit per test

input

output

n × n magic grid on the entrance which is filled with integers. Chris noticed that exactly one of the cells in the grid is empty, and to enter Udayland, they need to fill a positive integerinto the empty cell.

a magic square. This means that he has to fill in a positive integer so that the sum of the numbers in each row of the grid (

), each column of the grid (

), and the two long diagonals of the grid (the main diagonal —

and the secondary diagonal —

) are equal.

Chris doesn't know what number to fill in. Can you help Chris find the correct positive integer to fill in or determine that it is impossible?

Input

n (1 ≤ n ≤ 500) — the number of rows and columns of the magic grid.

n lines follow, each of them contains n integers. The j-th number in the i-th of them denotes ai, j (1 ≤ ai, j ≤ 109 or ai, j), the number in the i-th row and j-th column of the magic grid. If the corresponding cell is empty, ai, j will be equal to 0. Otherwise, ai, j is positive.

i, j (1 ≤ i, j ≤ n) such that ai, j.

Output

x (1 ≤ x ≤ 1018) that should be filled in the empty cell so that the whole grid becomes a magic square. If such positive integer x does not exist, output  - 1

If there are multiple solutions, you may print any of them.

Examples

input

34 0 2 3 5 7 8 1 6

output

9

input

41 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1

output

1

input

41 1 1 1 1 1 0 1 1 1 2 1 1 1 1 1

output

-1

Note

9

The sum of numbers in each row is:

4 + 9 + 2 = 3 + 5 + 7 = 8 + 1 + 6 = 15.

The sum of numbers in each column is:

4 + 3 + 8 = 9 + 5 + 1 = 2 + 7 + 6 = 15.

The sum of numbers in the two diagonals is:

4 + 5 + 6 = 2 + 5 + 8 = 15.

In the third sample case, it is impossible to fill a number in the empty square such that the resulting grid is a magic square.

题解：给你一个n*n的矩阵，然后保证矩阵中有且只有一个0，然后要你在0的位置变成一个数，使得矩阵的行，列，斜加起来都相等。让你求这个数。（1<=ans<=10^18）。记录0的位置，随便计算一下两行的sum，在check一下行，列，斜就可以啦。复杂度O(n^2)。注意特判n=1时，输出1。

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include #include #include #include #include #include #include

C. Coloring Trees

time limit per test

memory limit per test

input

output

n trees grow. They decided to be naughty and color the trees in the park. The trees are numbered with integers from 1 to n

i has color ci. ZS the Coder and Chris the Baboon recognizes only m different colors, so 0 ≤ ci ≤ m, where ci means that tree i is uncolored.

ci. They can color each of them them in any of the m colors from 1 to m. Coloring the i-th tree with color j requires exactly pi, j

beauty of a coloring of the trees as the minimum number of contiguous groups (each group contains some subsegment of trees) you can split all the n trees into so that each group contains trees of the same color. For example, if the colors of the trees from left to right are 2, 1, 1, 1, 3, 2, 2, 3, 1, 3, the beauty of the coloring is 7, since we can partition the trees into 7contiguous groups of the same color : {2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}.

exactly k. They need your help to determine the minimum amount of paint (in litres) needed to finish the job.

Please note that the friends can't color the trees that are already colored.

Input

n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100) — the number of trees, number of colors and beauty of the resulting coloring respectively.

n integers c1, c2, ..., cn (0 ≤ ci ≤ m), the initial colors of the trees. ci equals to 0 if the tree number i is uncolored, otherwise the i-th tree has color ci.

n lines follow. Each of them contains m integers. The j-th number on the i-th of them line denotes pi, j (1 ≤ pi, j ≤ 109) — the amount of litres the friends need to color i-th tree with color j. pi, j's are specified even for the initially colored trees, but such trees still can't be colored.

Output

k, print  - 1.

Examples

input

3 2 20 0 0 1 2 3 4 5 6

output

10

input

3 2 22 1 2 1 3 2 4 3 5

output

-1

input

3 2 22 0 0 1 3 2 4 3 5

output

5

input

3 2 32 1 2 1 3 2 4 3 5

output

0

Note

2, 1, 1 minimizes the amount of paint used, which equals to 2 + 3 + 5 = 10. Note that 1, 1, 1 would not be valid because the beauty of such coloring equals to 1 ({1, 1, 1}

3, so there is no valid coloring, and the answer is - 1.

k, so no paint is used and the answer is 0.

题解：给你n棵树，m种颜色的颜料。让你用这m种颜料去把没有颜色的树染色。0代表uncolored，其他数字代表有颜色且不能再染色。在给你m*n的矩阵，分别对应其颜料用量。问你最少要多少颜料才能把这些树染成k种颜色分明的树。dp题。

设dp[i][j][k]表示前i棵树，颜色为j，最后一棵树为k时使用最少的颜料。

复杂度O(n^4)。敢写敢过....

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include #include #include #include #include #include #include

D. Directed Roads

time limit per test

memory limit per test

input

output

n towns numbered from 1 to n.

n directed roads in the Udayland. i-th of them goes from town i to some other town ai (ai ≠ i). ZS the Coder can flip the direction of any road in Udayland, i.e. if it goes from town A to town B before the flip, it will go from town B to town A

confusing, if there is a sequence of distinct towns A1, A2, ..., Ak (k > 1) such that for every 1 ≤ i < k there is a road from town Ai to town Ai + 1 and another road from town Ak to town A1. In other words, the roads are confusing if some of them

2n variants) in initial configuration can he choose to flip such that after flipping each road in the set exactly once, the resulting network will not

Note that it is allowed that after the flipping there are more than one directed road from some town and possibly some towns with no roads leading out of it, or multiple roads between any pair of cities.

Input

n (2 ≤ n ≤ 2·105) — the number of towns in Udayland.

n integers a1, a2, ..., an (1 ≤ ai ≤ n, ai ≠ i), ai denotes a road going from town i to town ai.

Output

109.

Examples

input

32 3 1

output

6

input

42 1 1 1

output

8

input

52 4 2 5 3

output

28

Note

3 towns and 3 roads. The towns are numbered from 1 to 3 and the roads are

,

,

initially. Number the roads 1 to 3

{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}. Note that the empty set is invalid because if no roads are flipped, then towns 1, 2, 3 is form a directed cycle, so it is confusing. Similarly, flipping all roads is confusing too. Thus, there are a total of 6

not confusing.

题解：给你n个城镇，然后A(i)表示一条有向边：i-->A(i)。给你一个nn点nn边的无向图，你可以翻转任意几条边，但是每条边只能翻转一次，问你有多少种方案，使得这个图不存在环。对于当前的环，此时大小为num,那么我们可以不断选择1条、2条、n-1条边翻转使得环不存在。

ans+=2^(num)-2 就是2^num减去全部翻转，和全部不翻转的方案。对于不在环上的边：ans=ans*2^(n-num)。复杂度O(n)。

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include #include #include #include #include #include #include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。