Codeforces Round 184 (Div. 2)
A. Strange Addition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Unfortunately, Vasya can only sum pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place. For example, Vasya can sum numbers 505 and 50, but he cannot sum 1 and 4.

Vasya has a set of k distinct non-negative integers d1, d2, ..., dk.

Vasya wants to choose some integers from this set so that he could sum any two chosen numbers. What maximal number of integers can he choose in the required manner?

Input

The first input line contains integer k (1 ≤ k ≤ 100) — the number of integers.

The second line contains k distinct space-separated integers d1, d2, ..., dk (0 ≤ di ≤ 100).

Output

In the first line print a single integer n the maximum number of the chosen integers. In the second line print n distinct non-negative integers — the required integers.

If there are multiple solutions, print any of them. You can print the numbers in any order.

Examples
Input
4
100 10 1 0
Output
4
0 1 10 100
Input
3
2 70 3
Output
2
2 70
B. Continued Fractions
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

A continued fraction of height n is a fraction of form . You are given two rational numbers, one is represented as and the other one is represented as a finite fraction of height n. Check if they are equal.

Input

The first line contains two space-separated integers p, q (1 ≤ q ≤ p ≤ 1018) — the numerator and the denominator of the first fraction.

The second line contains integer n (1 ≤ n ≤ 90) — the height of the second fraction. The third line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1018) — the continued fraction.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

Print "YES" if these fractions are equal and "NO" otherwise.

Examples
Input
9 4
2
2 4
Output
YES
Input
9 4
3
2 3 1
Output
YES
Input
9 4
3
1 2 4
Output
NO
Note

In the first sample .

In the second sample .

In the third sample .

C. Ivan and Powers of Two
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Ivan has got an array of n non-negative integers a1, a2, ..., an. Ivan knows that the array is sorted in the non-decreasing order.

Ivan wrote out integers 2a1, 2a2, ..., 2an on a piece of paper. Now he wonders, what minimum number of integers of form 2b (b ≥ 0) need to be added to the piece of paper so that the sum of all integers written on the paper equalled 2v - 1 for some integer v (v ≥ 0).

Help Ivan, find the required quantity of numbers.

Input

The first line contains integer n (1 ≤ n ≤ 105). The second input line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 2·109). It is guaranteed that a1 ≤ a2 ≤ ... ≤ an.

Output

Print a single integer — the answer to the problem.

Examples
Input
4
0 1 1 1
Output
0
Input
1
3
Output
3
Note

In the first sample you do not need to add anything, the sum of numbers already equals 23 - 1 = 7.

In the second sample you need to add numbers 20, 21, 22.

D. Olya and Graph
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Olya has got a directed non-weighted graph, consisting of n vertexes and m edges. We will consider that the graph vertexes are indexed from 1 to n in some manner. Then for any graph edge that goes from vertex v to vertex u the following inequation holds: v < u.

Now Olya wonders, how many ways there are to add an arbitrary (possibly zero) number of edges to the graph so as the following conditions were met:

  1. You can reach vertexes number i + 1, i + 2, ..., n from any vertex number i (i < n).
  2. For any graph edge going from vertex v to vertex u the following inequation fulfills: v < u.
  3. There is at most one edge between any two vertexes.
  4. The shortest distance between the pair of vertexes i, j (i < j), for which j - i ≤ k holds, equals j - i edges.
  5. The shortest distance between the pair of vertexes i, j (i < j), for which j - i > k holds, equals either j - i or j - i - k edges.

We will consider two ways distinct, if there is the pair of vertexes i, j (i < j), such that first resulting graph has an edge from i to j and the second one doesn't have it.

Help Olya. As the required number of ways can be rather large, print it modulo 1000000007 (109 + 7).

Input

The first line contains three space-separated integers n, m, k (2 ≤ n ≤ 106, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106).

The next m lines contain the description of the edges of the initial graph. The i-th line contains a pair of space-separated integers ui, vi (1 ≤ ui < vi ≤ n) — the numbers of vertexes that have a directed edge from ui to vi between them.

It is guaranteed that any pair of vertexes ui, vi has at most one edge between them. It also is guaranteed that the graph edges are given in the order of non-decreasing ui. If there are multiple edges going from vertex ui, then it is guaranteed that these edges are given in the order of increasing vi.

Output

Print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Examples
Input
7 8 2
1 2
2 3
3 4
3 6
4 5
4 7
5 6
6 7
Output
2
Input
7 0 2
Output
12
Input
7 2 1
1 3
3 5
Output
0
Note

In the first sample there are two ways: the first way is not to add anything, the second way is to add a single edge from vertex 2 to vertex 5.

E. Playing with String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Two people play the following string game. Initially the players have got some string s. The players move in turns, the player who cannot make a move loses.

Before the game began, the string is written on a piece of paper, one letter per cell.

An example of the initial situation at s = "abacaba"

A player's move is the sequence of actions:

  1. The player chooses one of the available pieces of paper with some string written on it. Let's denote it is t. Note that initially, only one piece of paper is available.
  2. The player chooses in the string t = t1t2... t|t| character in position i (1 ≤ i ≤ |t|) such that for some positive integer l (0 < i - l; i + l ≤ |t|) the following equations hold: ti - 1 = ti + 1, ti - 2 = ti + 2, ..., ti - l = ti + l.
  3. Player cuts the cell with the chosen character. As a result of the operation, he gets three new pieces of paper, the first one will contain string t1t2... ti - 1, the second one will contain a string consisting of a single character ti, the third one contains string ti + 1ti + 2... t|t|.
An example of making action (i = 4) with string s = «abacaba»

Your task is to determine the winner provided that both players play optimally well. If the first player wins, find the position of character that is optimal to cut in his first move. If there are multiple positions, print the minimal possible one.

Input

The first line contains string s (1 ≤ |s| ≤ 5000). It is guaranteed that string s only contains lowercase English letters.

Output

If the second player wins, print in the single line "Second" (without the quotes). Otherwise, print in the first line "First" (without the quotes), and in the second line print the minimal possible winning move — integer i (1 ≤ i ≤ |s|).

Examples
Input
abacaba
Output
First
2
Input
abcde
Output
Second
Note

In the first sample the first player has multiple winning moves. But the minimum one is to cut the character in position 2.

In the second sample the first player has no available moves.