vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: ZgukistringZ

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Professor GukiZ doesn't accept string as they are. He likes to swap some letters in string to obtain a new one.

GukiZ has strings *a*, *b*, and *c*. He wants to obtain string *k* by swapping some letters in *a*, so that *k* should contain as many non-overlapping substrings equal either to *b* or *c* as possible. Substring of string *x* is a string formed by consecutive segment of characters from *x*. Two substrings of string *x* overlap if there is position *i* in string *x* occupied by both of them.

GukiZ was disappointed because none of his students managed to solve the problem. Can you help them and find one of possible strings *k*?

Input Specification:
The first line contains string *a*, the second line contains string *b*, and the third line contains string *c* (1<=≤<=|*a*|,<=|*b*|,<=|*c*|<=≤<=105, where |*s*| denotes the length of string *s*).

All three strings consist only of lowercase English letters. 

It is possible that *b* and *c* coincide.

Output Specification:
Find one of possible strings *k*, as described in the problem statement. If there are multiple possible answers, print any of them.

Demo Input:
['aaa\na\nb\n', 'pozdravstaklenidodiri\nniste\ndobri\n', 'abbbaaccca\nab\naca\n']

Demo Output:
['aaa', 'nisteaadddiiklooprrvz', 'ababacabcc']

Note:
In the third sample, this optimal solutions has three non-overlaping substrings equal to either *b* or *c* on positions 1 – 2 (*ab*), 3 – 4 (*ab*), 5 – 7 (*aca*). In this sample, there exist many other optimal solutions, one of them would be *acaababbcc*.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A penguin Rocher has $n$ sticks. He has exactly one stick with length $i$ for all $1 \le i \le n$.

He can connect some sticks. If he connects two sticks that have lengths $a$ and $b$, he gets one stick with length $a + b$. Two sticks, that were used in the operation disappear from his set and the new connected stick appears in his set and can be used for the next connections.

He wants to create the maximum number of sticks that have the same length. It is not necessary to make all sticks have the same length, some sticks can have the other length. How many sticks with the equal length he can create?


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Next $t$ lines contain descriptions of test cases.

For each test case, the only line contains a single integer $n$ ($1 \le n \le 10^{9}$).


-----Output-----

For each test case, print a single integer  — the answer to the problem.


-----Example-----
Input
4
1
2
3
4

Output
1
1
2
2



-----Note-----

In the third case, he can connect two sticks with lengths $1$ and $2$ and he will get one stick with length $3$. So, he will have two sticks with lengths $3$.

In the fourth case, he can connect two sticks with lengths $1$ and $3$ and he will get one stick with length $4$. After that, he will have three sticks with lengths $\{2, 4, 4\}$, so two sticks have the same length, and one stick has the other length.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A lottery is being held in a corner of the venue of the Aizu festival. Several types of balls are inside the lottery box and each type has its unique integer printed on the surfaces of the balls. An integer T is printed on the lottery box.

In the lottery, you first declare two integers A and B, and draw up to M balls from the box. Let the sum of the integers printed on the balls be S. You can get a wonderful gift if the following two criteria are met: S divided by T gives a remainder greater than or equal to A, and S divided by T gives a quotient (fractional portion dropped) greater than or equal to B.

Write a program to determine if you have any chance of getting the gift given the following information: the number of ball types, ball-type specific integers, the maximum number of balls to be drawn from the box, the integer printed on the lottery box, and two integers declared before drawing. Assume that each ball type has sufficient (≥M) population in the box. Note also that there may be a chance of getting the gift even without drawing any ball.



Input

The input is given in the following format.


N M T
a_1
a_2
:
a_N
Q
A_1 B_1
A_2 B_2
:
A_Q B_Q


The first line provides the number of ball types N(1≤N≤105), the maximum number of balls you can draw from the box M(1≤M≤105), and the integer printed on the box T(1≤T≤1000). Each of the subsequent N lines provides an integer a_i (1≤a_i≤109) printed on the i-th ball type. The next line following these provides the number of declarations Q (1≤Q≤105). Each of the Q lines following this provides a pair of integers A_i (0 ≤ A_i < T), B_i (0 ≤ B_i ≤ 109) that constitute the i-th declaration.

Output

Output a line for each pair of declaration A and B that contains "yes" if there is a chance of getting the gift or "no" otherwise.

Example

Input

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


Output

yes
no
yes
no
yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Make multiple functions that will return the sum, difference, modulus, product, quotient, and the exponent respectively.

Please use the following function names:


addition = **add**

multiply = **multiply**

division = **divide** (both integer and float divisions are accepted)

modulus = **mod**

exponential = **exponent**

subtraction = **subt**



*Note: All math operations will be:
a (operation) b*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
-----General Statement:-----
Read a number in scientific notation and output its equivalent decimal value.

-----Input:-----
All data is on a single line. The first integer indicates how many pairs of numbers follow. The first of each pair is A, the base number, and the second is E, the power of 10.

-----Output:-----
Round each answer to 2 decimal places. Trailing zeros to the right of the decimal point are required. A leading zero to the left of the decimal point is not required.
The output is to be formatted exactly like that for the sample output given below.

-----Assumptions:-----
E is in the range –10 .. 10. A is 1 or larger but less than 10.
Discussion: 
If A = 3.926 and E = 4, the number represented is 3.926 X 104 or 39260, which is 39260.00 when rounded to 2 decimal places.

-----Sample Input:-----
4 4.296 3 3.8 -2 1.8 2 2.8678 1

-----Sample Output:-----
4296.00
0.04
180.00
28.68

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's autumn now, the time of the leaf fall.
Sergey likes to collect fallen leaves in autumn. In his city, he can find fallen leaves of maple, oak and poplar. These leaves can be of three different colors: green, yellow or red.
Sergey has collected some leaves of each type and color. Now he wants to create the biggest nice bouquet from them. He considers the bouquet nice iff all the leaves in it are either from the same type of tree or of the same color (or both). Moreover, he doesn't want to create a bouquet with even number of leaves in it, since this kind of bouquets are considered to attract bad luck. However, if it's impossible to make any nice bouquet, he won't do anything, thus, obtaining a bouquet with zero leaves.
Please help Sergey to find the maximal number of leaves he can have in a nice bouquet, which satisfies all the above mentioned requirements.
Please note that Sergey doesn't have to use all the leaves of the same color or of the same type. For example, if he has 20 maple leaves, he can still create a bouquet of 19 leaves.

-----Input-----
IThe first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows."
The first line of each test case contains three space-separated integers MG MY MR denoting the number of green, yellow and red maple leaves respectively.
The second line contains three space-separated integers OG OY OR denoting the number of green, yellow and red oak leaves respectively.
The third line of each test case contains three space-separated integers PG PY PR denoting the number of green, yellow and red poplar leaves respectively.

-----Output-----
For each test case, output a single line containing the maximal amount of flowers in nice bouquet, satisfying all conditions or 0 if it's impossible to create any bouquet, satisfying the conditions.

-----Constraints-----

- 1 ≤ T ≤ 10000
- Subtask 1 (50 points): 0 ≤ MG, MY, MR, OG, OY, OR, PG, PY, PR ≤ 5
- Subtask 2 (50 points): 0 ≤ MG, MY, MR, OG, OY, OR, PG, PY, PR ≤ 109

-----Example-----
Input:1
1 2 3
3 2 1
1 3 4

Output:7

-----Explanation-----
Example case 1. We can create a bouquet with 7 leaves, for example, by collecting all yellow leaves. This is not the only way to create the nice bouquet with 7 leaves (for example, Sergey can use all but one red leaves), but it is impossible to create a nice bouquet with more than 7 leaves.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given N, consider a convex N-sided polygon with vertices labelled A[0], A[i], ..., A[N-1] in clockwise order.
Suppose you triangulate the polygon into N-2 triangles.  For each triangle, the value of that triangle is the product of the labels of the vertices, and the total score of the triangulation is the sum of these values over all N-2 triangles in the triangulation.
Return the smallest possible total score that you can achieve with some triangulation of the polygon.
 



Example 1:
Input: [1,2,3]
Output: 6
Explanation: The polygon is already triangulated, and the score of the only triangle is 6.


Example 2:

Input: [3,7,4,5]
Output: 144
Explanation: There are two triangulations, with possible scores: 3*7*5 + 4*5*7 = 245, or 3*4*5 + 3*4*7 = 144.  The minimum score is 144.


Example 3:
Input: [1,3,1,4,1,5]
Output: 13
Explanation: The minimum score triangulation has score 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13.

 
Note:

3 <= A.length <= 50
1 <= A[i] <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are times you recall a good old friend and everything you've come through together. Luckily there are social networks — they store all your message history making it easy to know what you argued over 10 years ago.

More formal, your message history is a sequence of messages ordered by time sent numbered from 1 to n where n is the total number of messages in the chat.

Each message might contain a link to an earlier message which it is a reply to. When opening a message x or getting a link to it, the dialogue is shown in such a way that k previous messages, message x and k next messages are visible (with respect to message x). In case there are less than k messages somewhere, they are yet all shown.

Digging deep into your message history, you always read all visible messages and then go by the link in the current message x (if there is one) and continue reading in the same manner.

Determine the number of messages you'll read if your start from message number t for all t from 1 to n. Calculate these numbers independently. If you start with message x, the initial configuration is x itself, k previous and k next messages. Messages read multiple times are considered as one.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ n) — the total amount of messages and the number of previous and next messages visible.

The second line features a sequence of integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} < i), where a_{i} denotes the i-th message link destination or zero, if there's no link from i. All messages are listed in chronological order. It's guaranteed that the link from message x goes to message with number strictly less than x.


-----Output-----

Print n integers with i-th denoting the number of distinct messages you can read starting from message i and traversing the links while possible.


-----Examples-----
Input
6 0
0 1 1 2 3 2

Output
1 2 2 3 3 3 

Input
10 1
0 1 0 3 4 5 2 3 7 0

Output
2 3 3 4 5 6 6 6 8 2 

Input
2 2
0 1

Output
2 2 



-----Note-----

Consider i = 6 in sample case one. You will read message 6, then 2, then 1 and then there will be no link to go.

In the second sample case i = 6 gives you messages 5, 6, 7 since k = 1, then 4, 5, 6, then 2, 3, 4 and then the link sequence breaks. The number of distinct messages here is equal to 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Villages were scattered in the Wakamatsu Plain of Aizu. Several settlements are connected by straight roads that allow them to travel to and from each other, and any settlement in the plain can be traced back and forth. Each road has a lengthy maintenance fee, but all the settlements funded the road to maintain it.

At one point, it was decided that all the settlements would be united in one village, and the boundaries surrounding the villages would be drawn. According to national rules, no straight line connecting any of the two settlements that make up a village should pass outside the village (it is permissible to pass on the border). In addition, in Aizu, there must be a road on the border that surrounds the village. Where there is no road on the border, the country will create a new one.

However, the village pays for the maintenance of the road, so the villagers want to keep the boundaries as short as possible. In addition, the villagers decided to minimize the total length of the roads by eliminating roads that were not on the border, while maintaining the ability to travel between all settlements.

Information on the location of the village and the original road is given. Create a program that calculates the minimum total length of the roads when the roads are on the border and all settlements are allowed to come and go. However, the village shall be a point with no size, and the road shall be a line segment with no width.



Input

The input is given in the following format.


VR
x1 y1
x2 y2
::
xV yV
s1 t1
s2 t2
::
sR tR


The number of settlements V (3 ≤ V ≤ 100) and the number of roads R (2 ≤ R ≤ 1000) are given in the first line.

The following V line gives information on the points that represent the settlement. The two integers xi, yi (-1000 ≤ xi, yi ≤ 1000) given in each row represent the x-coordinate and y-coordinate of the i-th settlement, respectively.

The following R line is given information on the original road. The two integers si, ti (1 ≤ si <ti ≤ V) given in each row indicate that the i-th road connects the si-th and ti-th settlements.

The input satisfies the following conditions.

* If i ≠ j, the coordinates of the i-th and j-th settlements are different.
* In each of the two settlements, there is at most one way to connect them directly.
* Two different roads do not share any points other than the endpoints.
* Three or more settlements are never lined up on the same straight line.

Output

The minimum value of the total length of roads that satisfy the conditions is output as a real number on one line. However, the error must not exceed plus or minus 0.001. If this condition is satisfied, any number of digits after the decimal point may be displayed.

Examples

Input

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


Output

11.4142


Input

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


Output

18.2521

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a given prime $\boldsymbol{p}$, define $\text{ord}_p(k)$ as the multiplicity of $\boldsymbol{p}$ in $\boldsymbol{\mbox{k}}$, i.e. the number of times $\boldsymbol{p}$ appears in the prime factorization of $\boldsymbol{k}$.

For a given $\boldsymbol{p}$ (prime) and $\boldsymbol{\mbox{L}}$, let $F(p,L)$ be the number of integers $n$ such that $1\leq n\leq L$ and $\text{ord}_p(n!)$ is divisible by $\boldsymbol{p}$. Here $n!$ denotes the factorial of $n$.

Your job is to calculate $F(p,L)$ given L$\boldsymbol{p}$ and $\boldsymbol{L}$.

Input Format 

The first line contains the number of test cases $\mathbf{T}$. 

Each of the next $\mathbf{T}$ lines contains two integers $\boldsymbol{p}$ and $\boldsymbol{\mbox{L}}$ separated by a space.

Output Format 

For each test case, output one line containing $F(p,L)$.

Constraints 

$1\leq T\leq1000000$ 

$2\leq p\leq10^{18}$ 

$1\leq L\leq10^{18}$ 

$\boldsymbol{p}$ is prime

Sample input  

2
2 6
3 6

Sample Output  

2
2

Explanation 

Here are the first 6 factorials: 1, 2, 6, 24, 120, 720.  

The multiplicities of 2 in these numbers are: 0, 1, 1, 3, 3, 4. 

Exactly two of these are divisible by 2 (0 and 4), so $F(2,6)=2$.

The multiplicities of 3 in these numbers are: 0, 0, 1, 1, 1, 2. 

Exactly two of these are divisible by 3 (0 and 0), so $F(3,6)=2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Valera has n counters numbered from 1 to n. Some of them are connected by wires, and each of the counters has a special button.

Initially, all the counters contain number 0. When you press a button on a certain counter, the value it has increases by one. Also, the values recorded in all the counters, directly connected to it by a wire, increase by one.

Valera and Ignat started having a dispute, the dispute is as follows. Ignat thought of a sequence of n integers a1, a2, ..., an. Valera should choose some set of distinct counters and press buttons on each of them exactly once (on other counters the buttons won't be pressed). If after that there is a counter with the number i, which has value ai, then Valera loses the dispute, otherwise he wins the dispute.

Help Valera to determine on which counters he needs to press a button to win the dispute.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105), that denote the number of counters Valera has and the number of pairs of counters connected by wires.

Each of the following m lines contains two space-separated integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi), that mean that counters with numbers ui and vi are connected by a wire. It is guaranteed that each pair of connected counters occurs exactly once in the input.

The last line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 105), where ai is the value that Ignat choose for the i-th counter.

Output

If Valera can't win the dispute print in the first line -1.

Otherwise, print in the first line integer k (0 ≤ k ≤ n). In the second line print k distinct space-separated integers — the numbers of the counters, where Valera should push buttons to win the dispute, in arbitrary order.

If there exists multiple answers, you are allowed to print any of them.

Examples

Input

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


Output

2
1 2


Input

4 2
1 2
3 4
0 0 0 0


Output

3
1 3 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let’s define a grid to be a set of tiles with 2 rows and 13 columns. Each tile has an English letter written in it. The letters don't have to be unique: there might be two or more tiles with the same letter written on them. Here is an example of a grid: ABCDEFGHIJKLM

NOPQRSTUVWXYZ 

We say that two tiles are adjacent if they share a side or a corner. In the example grid above, the tile with the letter 'A' is adjacent only to the tiles with letters 'B', 'N', and 'O'. A tile is not adjacent to itself.

A sequence of tiles is called a path if each tile in the sequence is adjacent to the tile which follows it (except for the last tile in the sequence, which of course has no successor). In this example, "ABC" is a path, and so is "KXWIHIJK". "MAB" is not a path because 'M' is not adjacent to 'A'. A single tile can be used more than once by a path (though the tile cannot occupy two consecutive places in the path because no tile is adjacent to itself).

You’re given a string s which consists of 27 upper-case English letters. Each English letter occurs at least once in s. Find a grid that contains a path whose tiles, viewed in the order that the path visits them, form the string s. If there’s no solution, print "Impossible" (without the quotes).


-----Input-----

The only line of the input contains the string s, consisting of 27 upper-case English letters. Each English letter occurs at least once in s.


-----Output-----

Output two lines, each consisting of 13 upper-case English characters, representing the rows of the grid. If there are multiple solutions, print any of them. If there is no solution print "Impossible".


-----Examples-----
Input
ABCDEFGHIJKLMNOPQRSGTUVWXYZ

Output
YXWVUTGHIJKLM
ZABCDEFSRQPON

Input
BUVTYZFQSNRIWOXXGJLKACPEMDH

Output
Impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the State of Takahashi in AtCoderian Federation, there are N cities, numbered 1, 2, ..., N.
M bidirectional roads connect these cities.
The i-th road connects City A_i and City B_i.
Every road connects two distinct cities.
Also, for any two cities, there is at most one road that directly connects them.
One day, it was decided that the State of Takahashi would be divided into two states, Taka and Hashi.
After the division, each city in Takahashi would belong to either Taka or Hashi.
It is acceptable for all the cities to belong Taka, or for all the cities to belong Hashi.
Here, the following condition should be satisfied:
 - Any two cities in the same state, Taka or Hashi, are directly connected by a road.
Find the minimum possible number of roads whose endpoint cities belong to the same state.
If it is impossible to divide the cities into Taka and Hashi so that the condition is satisfied, print -1.

-----Constraints-----
 - 2 \leq N \leq 700
 - 0 \leq M \leq N(N-1)/2
 - 1 \leq A_i \leq N
 - 1 \leq B_i \leq N
 - A_i \neq B_i
 - If i \neq j, at least one of the following holds: A_i \neq A_j and B_i \neq B_j.
 - If i \neq j, at least one of the following holds: A_i \neq B_j and B_i \neq A_j.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 B_1
A_2 B_2
:
A_M B_M

-----Output-----
Print the answer.

-----Sample Input-----
5 5
1 2
1 3
3 4
3 5
4 5

-----Sample Output-----
4

For example, if the cities 1, 2 belong to Taka and the cities 3, 4, 5 belong to Hashi, the condition is satisfied.
Here, the number of roads whose endpoint cities belong to the same state, is 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.