Problems - Codeforces

UFPE Starters Final Try-Outs 2018

Arthur is an extremely important person and rarely has the time to talk. To minimize the time spent with words, he developed his own language, which he uses on a daily basis. However, it's very hard to understand whatever comes out of his mouth.

In order to improve his interaction with the rest of the world, Arthur has asked the Narratives Industrial Complex (CIN in Portuguese) to develop a program which receives a speech S produced by Arthur and a pattern w and prints how many distinct ways we can obtain w by only removing characters from S. Two ways are considered distinct if there is an index 0 ≤ i < |S| such as S_i is present in one and not in the other.

Since you are considered the most experienced programmer in CIN, your team has trusted you the task of writing this program.

Input

The first line consists of a string S(1 ≤ |S| ≤ 10⁵), representing Arthur's speech. S contains only lower and upper case letters.

The second and last line consists of a string w(1 ≤ |w| ≤ 10), the pattern to be searched.

Output

Print a single integer: The number of distinct ways to obtain w by removing letters from S. Because this number can be large, print the remained of this number divided by 1000000007 = 10⁹ + 7

Examples

Input

weewrshkim
sim

Output

Input

qqqaaabbbcccfffrrr
qabcfr

Output

In the recent travel to Foz, the competitors entertained themselves playing Battleship. While discussing the best strategy to win the game, they had the idea of implementing a Battleship simulator.

This simulator should answer to the following types of query:

1. Place a ship in the map. If the placement of the ship would make it overlap with another, do not place it.
2. Sum the number of occupied cells in a segment of a line or column.

When the simulator starts, there are no ships placed in the map. All queries of type 1 have its size limited to 6 (which is the maximum ship size available in the game).

Unfortunately, they are too tired from playing Battleship and asked for your help to implement the simulator.

Input

The first line of input contains three integers: N, M, Q (1 ≤ N, M ≤ 10⁹ and 1 ≤ Q ≤ 10⁵). N and M are, respectively, the number of lines and columns in the map.

Each of the following Q lines describe a query. Each description starts with an integer $\text{[math]}$ .

If query_type = 1, then follows ship_type x y size ( $\text{[math]}$ ; 1 ≤ x ≤ M; 1 ≤ y ≤ N; and 1 ≤ size ≤ 6).
If query_type = 2, then follows range_type x y size ( $\text{[math]}$ ; 1 ≤ x ≤ M; 1 ≤ y ≤ N; and 1 ≤ size ≤ M if range_type = L, 1 ≤ size ≤ N otherwise).

If ship_type = L the ship is placed in a line. Otherwise, its place in a column. (The same is valid for range_type).

All ships are placed within the map boundaries.

Output

For each query of type 1, print -1 if it's not possible to place the ship in the given position.

For each query of type 2, print the quantity of cells which are occupied by a ship in the specified range.

Example

Input

Output

Diogo and Lucas are in São José dos Campos to participate in a programming competition. The event is happening this morning, so they must quickly find somewhere where they can eat.

Diogo looked in the map for the closest cafeterias from where they are and found two cafeterias (with distinct locations) which looked nice and asked Lucas to choose between them.

Lucas told him to choose the one closest to the event location and, if they are at the same distance, the one closest to their current location. Diogo, however, said they were tied in Lucas' criteria, and also the distance between the cafeterias and the event location is the same to their distance to the event.

Now Lucas is wondering if this is possible, and, if affirmative, what are the locations.

Input

The input consists of 5 integers, A_x, A_y, B_x, B_y, D (|A_x|, |A_y|, |B_x|, |B_y|, D ≤ 10⁴). Where (A_x, A_y) is their current position, (B_x, B_y) is the event's position and D is the their distance to the cafeterias.

Output

In the first line of the output print “YES” if it's possible and “NO” otherwise. If it's possible, the second line must contain 4 real numbers P_x, P_y, Q_x, Q_y, where (P_x, P_y) and (Q_x, Q_y) are the cafeteria locations.

The output must be within a maximum error of 10^- 5.

Examples

Input

0 5 0 0 7

Output

YES
-4.99899990 0.10000000 4.99899990 0.10000000

Input

0 5 0 0 100

Output

NO

The Inter-space Navigation Center (CIN in portuguese) launched a probe in a distant planet. To know its precise location, the Center will need to maintain a satellite following its steps. That way, the satellite needs first to find the probe in the terrain of the unknown planet, which can be considered a matrix of N lines and M columns.

While operating, the probe emits a log with the taken actions at each instant of time. Let (X_i, Y_i) be the position of the probe at instant i, these actions can be:

C: The probe moves upwards (X_i + 1 = X_i + 1)
D: The probe moves rightwards (Y_i + 1 = Y_i + 1)
B: The probe moves downwards (X_i + 1 = X_i - 1)
E: The probe moves leftwards (Y_i + 1 = Y_i - 1)

At instant T all the logs emited by the probe since instant 0 will be available. Your task is compute all positions that must be checked at instant T so that the probe is guaranteedly found.

The satellite is capable of analyzing as many positions as they're necessary, but you must not check any position for which there are enough data to determine that the probe can't be there.

Input

The first line contains 2 space separated integers, N and M (1 ≤ N, M ≤ 10⁶, 1 ≤ N × M ≤ 10⁶), the number of lines and the number of coulmns in the matrix.

The second line contains 1 integer T (1 ≤ T ≤ 10⁶), the current instant. T lines follow. The (i + 2)-th line contains 1 character, l_i ( $\text{[math]}$ ), the probe's log at instant i.

Output

In the first line, print 1 integer, Q (1 ≤ Q ≤ N * M), the number of positions to be verified.

Then, print Q lines. In the (j + 1)-th line, print 2 space separated integers, X_j (1 ≤ X_j ≤ N) and Y_j (1 ≤ Y_j ≤ N), the j-th coordinates of the matrix to be verified.

Examples

Input

3 3
3
D
D
B

Output

2
1 3
2 3

Input

1 3
1
E

Output

2
1 1
1 2

Guga was bored, so he decided to read the dictionary and learned a new word:

Palindrome: a word, phrase, or sequence that reads the same backward as forward.

madam, hannah, x e redivider are examples of palindromes.

Analyzing some words, Guga realized the most of them weren't palindromes and decided to create a new category called K-Palindrome, defined as follows:

K-Palindrome: a word, phrase or sequence that, by substituting K letters, is equivalent to a palindrome.

For example, xyz is not a palindrome, but is a 1-Palindrome, because we can substitute the x with a z and obtain zyz. On the other hand, abcb is neither a palindrome nor a 1-Palindrome, but it is a 2-Palindrome, for we can substitute two letters and obtain a palindrome.

With this new definition, Guga was able to find many more words that satisfied it.

While researching on palindromes, Guga discovered the following problem: given a string S, how many continuous substrings of S are palindromes?

Intrigued, he decided to create an equivalent problem: given a string S and an integer K, how many continuous substrings of S are K-palindromes?

Guga thinks it's very easy to find a wrong answer to his problem with large strings, and want a computer program that solve it. Help Guga (:

Input

Each test case consists of two lines.

The first line contains a string S (1 ≤ |S| ≤ 3000) composed only of lowercase letters, the string in which Guga wants to find the K-Palindromes.

The second line contains an integer K (0 ≤ K ≤ |S| / 2), the number of letters that can be substituted in S.

Output

The output consists of a single line containing an integer X, the number of substrings of S that are K-palindromes.

Examples

Input

ovo
1

Output

Input

ovo
0

Output

Note

By definition:

Every K-Palindrome is also a K'-Palindrome, where K' > K.
Every palindrome is a 0-palindrome.

On holidays, Bolado decided to go on an adventure. Bored with the urban life, he decided to travel to the mountains, where he'd have the time to discover new places and think in jokes. Upon his arrival, Bolado found himself surrounded by avast and dense forest, with trees of various types, which make his instincts lead him to the following thought.

"Why does the pine tree never gets lost in the woods?"

"Because he has a pine cone!"

(Read the statement in Portuguese to understand the joke)

Glad with the joke he made, Bolado could only think about it while looking for the inn. However, it didn't take too long until our beloved jokester noticed he was lost. Fortunately, he had a map of the area.

In the map there are N areas, numbered from 1 to N. Bolado is currently lost in the area 1 and the inn is in area N. There's also M directional paths which connect two distinct areas. Each path has also a description containing the time in minutes needed to cross it.

Additionally, because environmental preservation matters, P of the N areas have a pine tree. There are no pine trees in area 1 and area N. Whenever Bolado finds himself in one of these areas, he needs to stop and laugh for K seconds while remembering his master piece. There are T minutes left until the sun sets and Bolado wants to arrive at the inn ASAP (so he can think about inn related jokes).

Input

The first line contains five integers, N (2 ≤ N ≤ 3 * 10⁴), M (0 ≤ M ≤ 10⁵), T (0 ≤ T ≤ 5 * 10⁷), K (1 ≤ K ≤ 5 * 10⁷), P (0 ≤ P ≤ N - 2), as described above. Then follows P integers p_i ( $\text{[math]}$ ). After, there are M lines describing each path with three integers x_j, y_j and w_j, indicating that Bolado can go from area x_j to area y_j in w_j minutes, for 1 ≤ j ≤ M (x_j ≠ y_j; 1 ≤ x_j, y_j ≤ N and 1 ≤ w_j ≤ 10⁵).

Output

Print the minimum time Bolado can arrive at the inn. If he can't arrive before or at the same time the sun sets, print “-1” without the quotes.

Examples

Input

5 7 312 10 2
3 2
1 2 8
4 5 98
3 2 12
5 2 30
5 1 103
3 4 65
2 3 1

Output

Input

4 6 29370 22446 1
3
4 2 32014
2 3 24
2 1 67
4 3 16
1 2 633
2 4 4298

Output

Input

3 2 701 8561 1
2
2 1 346
3 1 9

Output

-1

Pixie is a very famous businessman who loves to give parties to his associates. One day he decided to organize a dinner like never before and gather all of his partners together. He asked a round table, so he can see everybody when he sits.

Pixie is a very friendly guy and has no restrictions on where he will sit. However, despite his contagious charisma, his partners only go to the the dinners on his account. In fact, they hate themselves so much (except for Pixie) that they fight if they sit close to each other. Consequently, they demand to sit apart at least R chairs from each other, so they can barely see their faces.

Pixie, a very curious man, would like to know in how many ways he can organize his partners in the table so there are no fights. However, he is too busy, and asks you to find this number for him.

You will receive the number N of chairs in the table (1 ≤ N ≤ 10⁵), the number C of partners (1 ≤ C ≤ N) and the minimum number R of chairs that must be placed in the middle of every partner (1 ≤ R ≤ N). Help Pixie find out in how many ways he can organize his guests.

Input

Three integers N, C and R, as described in the statement.

Output

Print the number of ways to organize the guests at the table. As this number can be very large, print it modulo (10⁹ + 7).

If it's not possible to place the guests at table respecting their restrictions, print - 1.

Examples

Input

9 3 2

Output

Input

10 2 1

Output

Note

Two ways are distinct if the set of chairs occupied by the partners is distinct or if the chair in which Pixie sits is distinct.

Coming back from Foz, Gabi and Divino were headed to the boarding gate. Gabi, hungry, realized the large quantity of Cheese Bread Houses in the way and wondered which way they should take so they can pass by the maximum number of Cheese Bread Houses. Divino, however, wasn't that hungry, and wanted to know which way would minimize the number of Cheese Bread Houses.

Additionally, the airport has a strange property. The walkways between each terminal are unidirectional and, if there is a path leaving from Terminal A to Terminal B, there is no path from Terminal B to Terminal A.

Initially they are at Terminal 1 and the Gate is at Terminal N.

Input

The first line of input contains 3 integers, N, C and M (1 ≤ N ≤ 10⁵, 1 ≤ C ≤ N, 1 ≤ M ≤ 10⁵), indicating, respectively, the number of terminals (identifies from 1 to N), Cheese Bread Houses and walkways. The second line contains C integers, the indices of the terminals that have a Cheese Bread House. Finally, the following M lines contain 2 integers v and w, indicating thar there is a walkway from v to w.

Output

The output must contain a single line with 2 space separated integers Min and Max, the minimum and maximum number of Cheese Bread Houses by which they may pass by when going from Terminal 1 to Terminal N.

Example

Input

Output

1 3

Tiago lives in a street with N houses, numbered from 1 to N, in which the first one is his. He decided to get out of Codeforces and visit a friend, but his head is stuck in a problem for several days. Because of that, he is bit distracted and is not paying attention to where he is going.

The walk can be represented by K steps, where if he is in house i in a step, $\text{[math]}$ is the probability of him being at house j in the next step. He wants to know what is the expected value of the house where he'll stop, but he is too distracted to solve this problem.

Input

The first line of input consists of two integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 10⁹). The next N lines contain each N integers, where the j-th number in the i-th line is A_ij (0 ≤ A_ij ≤ 10⁶) and the sum in each line is 10⁶.

Output

The answer can be represented as an irreducible fraction $\text{[math]}$ . Print the integer P * Q^- 1 modulo 10⁹ + 7 (Q^- 1 is the modular inverse of Q modulo 10⁹ + 7).

Examples

Input

2 2
500000 500000
500000 500000

Output

500000005

Input

4 24255
283383 274729 386113 55775
167247 49080 415640 368033
449168 182769 352198 15865
127605 304475 230640 337280

Output

96636490

Input

2 2
0 1000000
1000000 0

Output

Input

2 1
0 1000000
1000000 0

Output

Jenny works at BBB (Battery Bank of Brazil). She's in charge of optimizing the batteries' displacements, but can't solve the problem. Knowing you are a programmer, she asked for your help.

At BBB, the batteries are arranged in piles. In a bank, the batteries can't be discharged. So, when recharging then, the bank spends M energy units, where M is the size of the greatest pile. Each pile initially has a_i batteries.

There is a machine the can move a battery from pile i to pile j with cost b_i + c_j. Jenny has a limited budget of K for moving the batteries and the bank wants the minimum M possible at the end.

Input

The first line of input consists of the integers N and K (1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 10¹⁸). The following N lines contain a_i, b_i and c_i (0 ≤ a_i, b_i, c_i ≤ 10⁶).

Output

Print the minumum M possible.

Example

Input

Output

Lucas really wanted to create an interesting problem with strings, but he spent so much time thinking that he ended up with no creativity to create a better statement for this problem.

The problem he came up with is the following:

Given an array v of strings, answer these queries:

1. update(i, s) replaces the i-th position in the array with a string s.
2. vprefix(l, r, s) checks whether there is any string in the sub-array [l, r] which is a prefix of s.
3. sprefix(l, r, s) checks whether s is a prefix of any string in the sub-array [l, r].

Input

In the first line of input, there is an integer n (1 ≤ n ≤ 10⁵) indicating the size of the array v. The following n lines display the contents of the array, where the (i + 1)-th line is the string in the i-th position in the array.

In the (n + 2)-th line, there is an integer q (1 ≤ q ≤ 10⁵), the number of queries to be executed. The following q lines contain the description of the q queries, one per line.

Each query is described as follows:

Type 1: 1 i s, where i is an integer (1 ≤ i ≤ n) and s is a string.
Type 2: 2 l r s, where l and r are integers (1 ≤ l ≤ r ≤ n) and s is a string.
Type 3: 3 l r s, where l and r are integers (1 ≤ l ≤ r ≤ n) and s is a string.

Output

For each query of type 2 and 3, print "Y" if the query's answer is true or "N" if it's false.

Example

Input

3
aaa
ab
acc
10
2 1 3 abb
2 3 3 abb
2 1 1 aaa
3 1 3 a
3 1 3 ac
3 3 3 b
3 3 3 ac
3 1 3 e
1 1 eae
3 1 3 e

Output

Y
N
Y
Y
Y
N
Y
N
Y

Note

The sum of the lengths of the strings initially in the array does not exceed 5 * 10⁵.
The sum of the lengths of the strings in the queries does not exceed 5 * 10⁵.
All strings contain only lower case characters.
String a is a prefix of string b if: $\text{[math]}$ .