2018 Yandex.Algorithm - Elimination Stage, Online Round 1
A. Police Patrol
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Nswill consists of n houses arranged in a row and numbered from 1 to n. One patrol car can be responsible for some segment of length no more than k. For example, segment of houses from some l to l + k - 1 inclusive. That means, if any crime happens in a single house on this segment corresponding police patrol will immediately start investigation.

Safety requirements say that the patrols should be assigned in such a way, that if two crimes happen simultaneously in any two different houses, there will be two distinct patrols that can immediately take care of them.

What is the minimum required number of patrols to ensure safety in Nswill?

Input

The only line of the input contains two integers n and k (2 ≤ k ≤ n ≤ 109) — the number of houses in Nswill and the maximum length of a segment that one police patrol can take care of.

Output

Output a single integer, the minimum number of patrols required.

Examples
Input
5 5
Output
2
Input
3 2
Output
2
Input
4 2
Output
3
Input
7 4
Output
4
Note

In the first sample, we can have both patrols cover the entire neighborhood.

For the second sample, we can have one patrol cover houses 1 and 2, while the other patrol covers houses 2 and 3.

For the third sample, we can have one patrol cover houses 1 and 2, another one cover 2 and 3, while the last cover 3 and 4. For example, if a crime occurs in houses 3 and 4, we can have the second patrol investigate house 3 and the third patrol investigate house 4.

For the last sample, one example of 4 patrols that work is the first and second patrol covers houses 1, 2, 3 and 4, and the third and fourth patrol cover houses 4, 5, 6 and 7.

B. Alphabetic Subsequence
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Davy has a string s consisting of digits '0' to '9'. He wants to replace each digit '0' to '9' with a unique character from 'a' to 'j' in such a way that two equal digits are always replaced with the same character, while two distinct digits are always replaced with distinct characters. Davy is interested in such replacements that there exists a subsequence of the string that is 'abcdefghij'.

Count the number of ways he can do the replacements so that this condition is satisfied. Two replacements are considered to be distinct if there exists a digit that is replaced with distinct characters in these two replacements.

Input

The only line of the input contains a string s consisting of digits from '0' to '9'. The string is non-empty and its length doesn't exceed 100.

Output

Print out a single integer, the number of ways to do replacement that satisfy all the conditions given in the problem statement.

Examples
Input
0123456789
Output
1
Input
01234567899876543210
Output
512

C. Infinite Graph Game
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Eugene has an undirected graph with n nodes and m edges. The nodes are labeled from 1 to n. The i-th node initially has value vi. Eugene also has some sequence of nodes s1, s2, ..., sk. Nodes can appear in this sequence in arbitrary order, two neighboring elements of the sequence are not necessary neighboring nodes of the graph. Moreover, two neighboring elements can stand for the same node. Each node can appear in this sequence arbitrary (possibly zero) number of times.

Eugene plays the following game starting at second 0 infinitely:

  1. On the i-th second, he chooses node .
  2. Adds to his score the value of all neighbors of x.
  3. Divide the value vx by 2. Note that we consider standard division, not integer. Thus, real value vx can turn to be non-integer.

Let li be Eugene's score after the i-th second. If sequence li grows infinitely large, print -1.

Otherwise, as sequence li is non-decreasing and doesn't go infinitely large, it has a limit. Moreover, one can show that this limit a rational number and can be represented as , where P and Q are coprime integers.

Under the given constraints, it is guaranteed that Q is not divisible by 109 + 7.

Print the value of P·Q - 1 modulo 109 + 7.

Here Q - 1 denotes the multiplicative inverse of Q modulo 109 + 7.

Input

The first line of the input contains three integers n, m and k (1 ≤ n, m, k ≤ 100 000) — the number of nodes in the graph, the number of edges and the length of sequence s.

The next line of the input contains n integers, v1, v2, ..., vn (0 ≤ vi ≤ 109) — initial values of each node.

The next line of input contains k integers, s1, s2, ..., sk (1 ≤ si ≤ n) — the sequence Eugene uses to consider nodes.

Each of the next m lines of the input contains two integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), that denote an undirected edge between corresponding nodes. It is guaranteed that each pair of nodes is connected by no more than one edge.

Output

Print a single integer, the answer to the problem.

Example
Input
4 3 4
1 1 1 1
1 2 3 4
1 2
2 3
1 3
Output
9
Note

For the sample, Eugene will choose nodes 1, 2, 3, 4, 1, 2, 3, 4, ...

The first few steps looks as follows:

  1. Choose node 1. Its value becomes . We add 2 to his score.
  2. Choose node 2. Its value becomes . We add to his score.
  3. Choose node 3. Its value becomes . We add 1 to his score.
  4. Choose node 4. Value v4 becomes . We add 0 to his score.
After one phase, his score is .

If we continue this infinitely, we can show that the limit of his score is equal to 9.

D. Stamp Stamp Stamp
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Cat Noku has a strip of paper that consists of n blank cells lying side by side. He has a painting s he wants to paint. This means, he would like to paint it so that the the i-th cell will contain color si (here, colors are represented by letters 'a'-'z'). He is not allowed to shift, turn or flip the strip. We consider that at the beginning each cell has no color assigned to it.

Cat Noku only has enough money to buy a single stamp. The stamp will consist of k units (1 ≤ k ≤ n), and each section is colored some arbitrary color. We denote the colors of the stamp as t1, t2, ..., tk. However, the value of k and exact colors of the stamp are yet to be defined.

To use the stamp, it must first be aligned with exactly k of the neighboring units on the paper. The stamp cannot extend beyond the ends of the paper, nor can it cover fractions of units. Once placed, the stamp paints the k covered units so that the i-th section from the left is painted color i. It is not allowed to turn or flip the stamp. It is allowed that the cell of the strip is colored multiple times, possible with different colors. The final color of the strip cell is equal to the color of the last stamp cell that was placed on it.

Given the string s, output the stamps that Cat Noku could have chosen to paint the string. Output these stamps in lexicographic order.

Input

The first and only line of input contains a single string s (1 ≤ |s| ≤ 150).

Output

Print the stamps that could have produced this string in lexicographic increasing order.

Examples
Input
aaaaa
Output
a
aa
aaa
aaaa
aaaaa
Input
babaaba
Output
ba
baaba
baba
babaaba
Note

In the second sample, Cat Noku can stamp out babaaba from ba as follows:

  1. ...ba..
  2. ..baa..
  3. babaa..
  4. babaaba

E. Increasing Sequence
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

April has a sequence of non-negative integers x1, x2, ..., xn.

She would like to make this sequence strictly increasing.

To do this, she can choose a non-negative integer k, and replace some of the xi with k - xi. In addition, after this replacement, all elements of the sequence must be non-negative.

Determine if there is some valid k that lets April get a strictly increasing sequence.

If there are multiple solutions, print any of them. If there are no solutions, print -1.

The output k must not exceed 2·109 + 1. It is guaranteed if a solution exists, there is a solution that doesn't exceed 2·109 + 1.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000), the length of the sequence.

The next line contains n integers x1, x2, ..., xn (0 ≤ xi ≤ 109).

Output

If there is no solution, print -1. Otherwise, on the first line, print a single non-negative integer k (0 ≤ k ≤ 2·109 + 1).

The next line contains n integers y1, y2, ..., yn (yi = xi or yi = k - xi, yi < yi + 1, 0 ≤ y0).

Examples
Input
3
5 2 1
Output
5
0 2 4
Input
5
1 2 5 3 2
Output
8
1 2 3 5 6
Input
3
1 1 1
Output
-1

F. Yet Another Binary Matrix
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For this problem, we will be working in the field mod 2.

Harry has a n × n binary matrix.

Let R denote some set of rows of this matrix, and C denote some set of columns of this matrix. Let W(P, Q) be a |P| by |Q| matrix, where the element in the i-th row and j-th column is equal to the element in the P[i]-th and Q[j]-th row of the given matrix. Notation S[i] means the i-th by value element of set S.

Harry has a subset of the row indices A, and a subset of column indices B.

He would like you to find a subset of column indices X such that the following conditions hold:

  1. X is disjoint from B.
  2. The rows of W(A, X + B) are linearly independent (see below for definition).
  3. The rows of W(R - A, C - X - B) are linearly independent.

If no solution exists, print -1. Otherwise, print any valid subset X.

A set of rows is called linearly independent if and only if there is no subset of rows that sums to a row with all zeros. Remember we are working mod 2, so for example, the rows [1, 0, 1], [1, 1, 0], [0, 1, 1] are not linearly independent since the sum of all these rows is zero. Informally, if we consider each row as a base-2 integer, there is no subset of them that xor to zero.

Input

The first line will contain three integers n, a and b (0 ≤ a, b ≤ n, 1 ≤ n ≤ 50).

The next line will contain a integers, the row indices A1, A2, ..., Aa (1 ≤ Ai ≤ n). These indices will be distinct. If a = 0, this line will be left blank.

The next line will contain b integers, the column indices of B1, B2, ..., Bb (1 ≤ Bi ≤ n). These indices will be distinct. If b = 0, this line will be left blank.

The next n lines will contain a binary string of length n, representing the binary matrix.

Output

If no solution exists, print -1.

Otherwise, on the first line, print an integer x, the size of your subset X (0 ≤ x ≤ n). The next line should contain x integers, the column indices of X. These indices must be distinct and disjoint from B.

Examples
Input
3 1 0
2

001
010
101
Output
1
2
Input
2 1 0
1

11
10
Output
1
2
Input
2 0 0


11
11
Output
-1
Input
6 4 1
1 4 2 3
2
101010
010101
110000
001100
000001
100000
Output
3
3 4 5