vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Automatons, or Finite State Machines (FSM), are extremely useful to programmers when it comes to software design. You will be given a simplistic version of an FSM to code for a basic TCP session.

The outcome of this exercise will be to return the correct state of the TCP FSM based on the array of events given.

---------------------------------

The input array of events will consist of one or more of the following strings:

```
APP_PASSIVE_OPEN, APP_ACTIVE_OPEN, APP_SEND, APP_CLOSE, APP_TIMEOUT, RCV_SYN, RCV_ACK, RCV_SYN_ACK, RCV_FIN, RCV_FIN_ACK
```

---------------------------------

The states are as follows and should be returned in all capital letters as shown:

```
CLOSED, LISTEN, SYN_SENT, SYN_RCVD, ESTABLISHED, CLOSE_WAIT, LAST_ACK, FIN_WAIT_1, FIN_WAIT_2, CLOSING, TIME_WAIT
```

---------------------------------

The input will be an array of events. Your job is to traverse the FSM as determined by the events, and return the proper state as a string, all caps, as shown above.

If an event is not applicable to the current state, your code will return `"ERROR"`.

### Action of each event upon each state:
(the format is `INITIAL_STATE: EVENT -> NEW_STATE`)

```
CLOSED: APP_PASSIVE_OPEN -> LISTEN
CLOSED: APP_ACTIVE_OPEN  -> SYN_SENT
LISTEN: RCV_SYN          -> SYN_RCVD
LISTEN: APP_SEND         -> SYN_SENT
LISTEN: APP_CLOSE        -> CLOSED
SYN_RCVD: APP_CLOSE      -> FIN_WAIT_1
SYN_RCVD: RCV_ACK        -> ESTABLISHED
SYN_SENT: RCV_SYN        -> SYN_RCVD
SYN_SENT: RCV_SYN_ACK    -> ESTABLISHED
SYN_SENT: APP_CLOSE      -> CLOSED
ESTABLISHED: APP_CLOSE   -> FIN_WAIT_1
ESTABLISHED: RCV_FIN     -> CLOSE_WAIT
FIN_WAIT_1: RCV_FIN      -> CLOSING
FIN_WAIT_1: RCV_FIN_ACK  -> TIME_WAIT
FIN_WAIT_1: RCV_ACK      -> FIN_WAIT_2
CLOSING: RCV_ACK         -> TIME_WAIT
FIN_WAIT_2: RCV_FIN      -> TIME_WAIT
TIME_WAIT: APP_TIMEOUT   -> CLOSED
CLOSE_WAIT: APP_CLOSE    -> LAST_ACK
LAST_ACK: RCV_ACK        -> CLOSED
```

!["EFSM TCP" ](http://theangelfallseries.com/img/EFSM_TCP.png)

## Examples

```
["APP_PASSIVE_OPEN", "APP_SEND", "RCV_SYN_ACK"] =>  "ESTABLISHED"

["APP_ACTIVE_OPEN"] =>  "SYN_SENT"

["APP_ACTIVE_OPEN", "RCV_SYN_ACK", "APP_CLOSE", "RCV_FIN_ACK", "RCV_ACK"] =>  "ERROR"
```

 

This kata is similar to [Design a Simple Automaton (Finite State Machine)](https://www.codewars.com/kata/design-a-simple-automaton-finite-state-machine), and you may wish to try that kata before tackling this one.

See wikipedia page [Transmission Control Protocol]( http://en.wikipedia.org/wiki/Transmission_Control_Protocol)
for further details.

See http://www.medianet.kent.edu/techreports/TR2005-07-22-tcp-EFSM.pdf page 4, for the FSM diagram used for this kata.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S of '(' and ')' parentheses, we add the minimum number of parentheses ( '(' or ')', and in any positions ) so that the resulting parentheses string is valid.
Formally, a parentheses string is valid if and only if:

It is the empty string, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Given a parentheses string, return the minimum number of parentheses we must add to make the resulting string valid.
 
Example 1:
Input: "())"
Output: 1


Example 2:
Input: "((("
Output: 3


Example 3:
Input: "()"
Output: 0


Example 4:
Input: "()))(("
Output: 4
 



Note:

S.length <= 1000
S only consists of '(' and ')' characters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A Martian boy is named s — he has got this name quite recently from his parents for his coming of age birthday. Now he enjoys looking for his name everywhere. If he sees that he can obtain his name from some string by removing zero or more letters (at that, the remaining letters remain in the same order), he gets happy. For example, if s=«aba», then strings «baobab», «aabbaa», «helloabahello» make him very happy and strings «aab», «baaa» and «helloabhello» do not.

However rather than being happy once, he loves twice as much being happy twice! So, when he got string t as a present, he wanted to cut it in two parts (the left part and the right part) so that each part made him happy.

Help s determine the number of distinct ways to cut the given string t into two parts in the required manner.

Input

The first line contains string s, consisting of lowercase English letters. The length of string s is from 1 to 1000 letters.

The second line contains string t, that also consists of lowercase English letters. The length of string t is from 1 to 106 letters.

Output

Print the sought number of ways to cut string t in two so that each part made s happy. 

Examples

Input

aba
baobababbah


Output

2


Input

mars
sunvenusearthmarsjupitersaturnuranusneptune


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your goal is to implement the method **meanVsMedian** which accepts an *odd-length* array of integers and returns one of the following:

* 'mean' - in case **mean** value is **larger than** median value
* 'median' - in case **median** value is **larger than** mean value
* 'same' - in case both mean and median share the **same value**

Reminder: [Median](https://en.wikipedia.org/wiki/Median)

Array will always be valid (odd-length >= 3)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has N days of summer vacation.
His teacher gave him M summer assignments. It will take A_i days for him to do the i-th assignment.
He cannot do multiple assignments on the same day, or hang out on a day he does an assignment.
What is the maximum number of days Takahashi can hang out during the vacation if he finishes all the assignments during this vacation?
If Takahashi cannot finish all the assignments during the vacation, print -1 instead.

-----Constraints-----
 - 1 \leq N \leq 10^6
 - 1 \leq M \leq 10^4
 - 1 \leq A_i \leq 10^4

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 ... A_M

-----Output-----
Print the maximum number of days Takahashi can hang out during the vacation, or -1.

-----Sample Input-----
41 2
5 6

-----Sample Output-----
30

For example, he can do the first assignment on the first 5 days, hang out on the next 30 days, and do the second assignment on the last 6 days of the vacation. In this way, he can safely spend 30 days hanging out.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob are playing a game of coins. N coins are placed on the table in a row. 

The game begins with Alice and afterwards they alternate the moves.

A valid move is defined as follows:

You pick one coin or two adjacent coins and remove them.

The game is over if anyone is not able to make any valid move, and the other person wins.

Given N, print "Alice" or "Bob" corresponding to who wins the game.

Input:

First line contains T, the number of testcases. Each testcase consists of N(the number of coins) in one line.

Output:

For each testcase, print the solution.

Constraints:

1 ≤ T ≤100

1 ≤ N ≤ 10^9

SAMPLE INPUT
2
1
3

SAMPLE OUTPUT
Alice
Alice

Explanation

In first testcase, Alice removes the only coin to win the game.
Let the coins be numbered 1 to 3 from left to right. In second testcase, Alice removes coin numbered 2. Now Bob cannot win the game.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Makoto has a big blackboard with a positive integer $n$ written on it. He will perform the following action exactly $k$ times:

Suppose the number currently written on the blackboard is $v$. He will randomly pick one of the divisors of $v$ (possibly $1$ and $v$) and replace $v$ with this divisor. As Makoto uses his famous random number generator (RNG) and as he always uses $58$ as his generator seed, each divisor is guaranteed to be chosen with equal probability.

He now wonders what is the expected value of the number written on the blackboard after $k$ steps.

It can be shown that this value can be represented as $\frac{P}{Q}$ where $P$ and $Q$ are coprime integers and $Q \not\equiv 0 \pmod{10^9+7}$. Print the value of $P \cdot Q^{-1}$ modulo $10^9+7$.


-----Input-----

The only line of the input contains two integers $n$ and $k$ ($1 \leq n \leq 10^{15}$, $1 \leq k \leq 10^4$).


-----Output-----

Print a single integer — the expected value of the number on the blackboard after $k$ steps as $P \cdot Q^{-1} \pmod{10^9+7}$ for $P$, $Q$ defined above.


-----Examples-----
Input
6 1

Output
3

Input
6 2

Output
875000008

Input
60 5

Output
237178099



-----Note-----

In the first example, after one step, the number written on the blackboard is $1$, $2$, $3$ or $6$ — each occurring with equal probability. Hence, the answer is $\frac{1+2+3+6}{4}=3$.

In the second example, the answer is equal to $1 \cdot \frac{9}{16}+2 \cdot \frac{3}{16}+3 \cdot \frac{3}{16}+6 \cdot \frac{1}{16}=\frac{15}{8}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given ${D}$ datasets where each dataset is in the form of two integers, $m$ and ${a}$, such that:
$n=\prod\limits_{i=1}^m p_i^{a+i},\text{where}~p_i~\text{is the}~i^{th}~\text{prime}.$

For each dataset, find and print the following on a new line: 

$\sum_{d|n}\sigma_0(d)$  

where $\sigma_0(x)$ is the count of divisors of ${x}$. As the answer can be quite large, print the result of this value modulo $(10^9+7)$.  

Input Format

The first line contains an integer, ${D}$, denoting the number of datasets. 

Each line ${i}$ of the ${D}$ subsequent lines contains two space-separated integers describing the respective values of $m_i$ and $a_i$ for dataset ${i}$.  

Constraints

$1\leq D\leq10^5$  
$1\leq m\leq10^5$  
$0\leq a\leq10^5$

Output Format

For each dataset, print a single integer denoting the result of the summation above modulo $(10^9+7)$ on a new line.

Sample Input
3
2 0
3 0
2 4

Sample Output
18
180
588

Explanation

For the first dataset where $m=2$ and ${a}=0$,
$\begin{aligned}&n=2^1\times3^2\\\Rightarrow&2\times9\\\Rightarrow&18$
$18}$ has the following divisors: $\{1,2,3,6,9,18\}$. Therefore, the result is:

$\begin{aligned}&\sigma_0(1)+\sigma_0(2)+\sigma_0(3)+\sigma_0(6)+\sigma_0(9)+\sigma_0(18)\\ \Rightarrow&1+2+2+4+3+6\\ \Rightarrow&18\end{aligned}$

Thus we print the value of $18\%(10^9+7)=18$ on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Choosing Capital for Treeland

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The country Treeland consists of *n* cities, some pairs of them are connected with unidirectional roads. Overall there are *n*<=-<=1 roads in the country. We know that if we don't take the direction of the roads into consideration, we can get from any city to any other one.

The council of the elders has recently decided to choose the capital of Treeland. Of course it should be a city of this country. The council is supposed to meet in the capital and regularly move from the capital to other cities (at this stage nobody is thinking about getting back to the capital from these cities). For that reason if city *a* is chosen a capital, then all roads must be oriented so that if we move along them, we can get from city *a* to any other city. For that some roads may have to be inversed.

Help the elders to choose the capital so that they have to inverse the minimum number of roads in the country.

Input Specification:
The first input line contains integer *n* (2<=≤<=*n*<=≤<=2·105) — the number of cities in Treeland. Next *n*<=-<=1 lines contain the descriptions of the roads, one road per line. A road is described by a pair of integers *s**i*,<=*t**i* (1<=≤<=*s**i*,<=*t**i*<=≤<=*n*; *s**i*<=≠<=*t**i*) — the numbers of cities, connected by that road. The *i*-th road is oriented from city *s**i* to city *t**i*. You can consider cities in Treeland indexed from 1 to *n*.

Output Specification:
In the first line print the minimum number of roads to be inversed if the capital is chosen optimally. In the second line print all possible ways to choose the capital — a sequence of indexes of cities in the increasing order.

Demo Input:
['3\n2 1\n2 3\n', '4\n1 4\n2 4\n3 4\n']

Demo Output:
['0\n2 \n', '2\n1 2 3 \n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this challenge, the user enters a string and a substring. You have to print the number of times that the substring occurs in the given string. String traversal will take place from left to right, not from right to left. 

NOTE: String letters are case-sensitive.

Input Format  

The first line of input contains the original string. The next line contains the substring.

Constraints  

$1\leq len(string)\leq200$ 

Each character in the string is an ascii character. 

Output Format 

Output the integer number indicating the total number of occurrences of the substring in the original string. 

Sample Input

ABCDCDC
CDC

Sample Output

2

Concept

Some string processing examples, such as these, might be useful. 

There are a couple of new concepts: 

In Python, the length of a string is found by the function len(s), where $\boldsymbol{\mathrm{~S~}}$ is the string. 

To traverse through the length of a string, use a for loop:  

for i in range(0, len(s)):
    print (s[i])

A range function is used to loop over some length: 

range (0, 5)

Here, the range loops over $\mbox{o}$ to $\begin{array}{c}A\end{array}$. $5$ is excluded.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bad news came to Mike's village, some thieves stole a bunch of chocolates from the local factory! Horrible! 

Aside from loving sweet things, thieves from this area are known to be very greedy. So after a thief takes his number of chocolates for himself, the next thief will take exactly k times more than the previous one. The value of k (k > 1) is a secret integer known only to them. It is also known that each thief's bag can carry at most n chocolates (if they intend to take more, the deal is cancelled) and that there were exactly four thieves involved. 

Sadly, only the thieves know the value of n, but rumours say that the numbers of ways they could have taken the chocolates (for a fixed n, but not fixed k) is m. Two ways are considered different if one of the thieves (they should be numbered in the order they take chocolates) took different number of chocolates in them.

Mike want to track the thieves down, so he wants to know what their bags are and value of n will help him in that. Please find the smallest possible value of n or tell him that the rumors are false and there is no such n.


-----Input-----

The single line of input contains the integer m (1 ≤ m ≤ 10^15) — the number of ways the thieves might steal the chocolates, as rumours say.


-----Output-----

Print the only integer n — the maximum amount of chocolates that thieves' bags can carry. If there are more than one n satisfying the rumors, print the smallest one.

If there is no such n for a false-rumoured m, print  - 1.


-----Examples-----
Input
1

Output
8

Input
8

Output
54

Input
10

Output
-1



-----Note-----

In the first sample case the smallest n that leads to exactly one way of stealing chocolates is n = 8, whereas the amounts of stealed chocolates are (1, 2, 4, 8) (the number of chocolates stolen by each of the thieves).

In the second sample case the smallest n that leads to exactly 8 ways is n = 54 with the possibilities: (1, 2, 4, 8),  (1, 3, 9, 27),  (2, 4, 8, 16),  (2, 6, 18, 54),  (3, 6, 12, 24),  (4, 8, 16, 32),  (5, 10, 20, 40),  (6, 12, 24, 48).

There is no n leading to exactly 10 ways of stealing chocolates in the third sample case.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.

There are $n$ displays placed along a road, and the $i$-th of them can display a text with font size $s_i$ only. Maria Stepanovna wants to rent such three displays with indices $i < j < k$ that the font size increases if you move along the road in a particular direction. Namely, the condition $s_i < s_j < s_k$ should be held.

The rent cost is for the $i$-th display is $c_i$. Please determine the smallest cost Maria Stepanovna should pay.


-----Input-----

The first line contains a single integer $n$ ($3 \le n \le 3\,000$) — the number of displays.

The second line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($1 \le s_i \le 10^9$) — the font sizes on the displays in the order they stand along the road.

The third line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 10^8$) — the rent costs for each display.


-----Output-----

If there are no three displays that satisfy the criteria, print -1. Otherwise print a single integer — the minimum total rent cost of three displays with indices $i < j < k$ such that $s_i < s_j < s_k$.


-----Examples-----
Input
5
2 4 5 4 10
40 30 20 10 40

Output
90

Input
3
100 101 100
2 4 5

Output
-1

Input
10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13

Output
33



-----Note-----

In the first example you can, for example, choose displays $1$, $4$ and $5$, because $s_1 < s_4 < s_5$ ($2 < 4 < 10$), and the rent cost is $40 + 10 + 40 = 90$.

In the second example you can't select a valid triple of indices, so the answer is -1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's the year 5555. You have a graph, and you want to find a long cycle and a huge independent set, just because you can. But for now, let's just stick with finding either.

Given a connected graph with $n$ vertices, you can choose to either:

  find an independent set that has exactly $\lceil\sqrt{n}\rceil$ vertices.

 find a simple cycle of length at least $\lceil\sqrt{n}\rceil$. 

An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice. I have a proof you can always solve one of these problems, but it's too long to fit this margin.


-----Input-----

The first line contains two integers $n$ and $m$ ($5 \le n \le 10^5$, $n-1 \le m \le 2 \cdot 10^5$) — the number of vertices and edges in the graph.

Each of the next $m$ lines contains two space-separated integers $u$ and $v$ ($1 \le u,v \le n$) that mean there's an edge between vertices $u$ and $v$. It's guaranteed that the graph is connected and doesn't contain any self-loops or multiple edges.


-----Output-----

If you choose to solve the first problem, then on the first line print "1", followed by a line containing $\lceil\sqrt{n}\rceil$ distinct integers not exceeding $n$, the vertices in the desired independent set.

If you, however, choose to solve the second problem, then on the first line print "2", followed by a line containing one integer, $c$, representing the length of the found cycle, followed by a line containing $c$ distinct integers integers not exceeding $n$, the vertices in the desired cycle, in the order they appear in the cycle.


-----Examples-----
Input
6 6
1 3
3 4
4 2
2 6
5 6
5 1

Output
1
1 6 4
Input
6 8
1 3
3 4
4 2
2 6
5 6
5 1
1 4
2 5

Output
2
4
1 5 2 4
Input
5 4
1 2
1 3
2 4
2 5

Output
1
3 4 5 


-----Note-----

In the first sample:

[Image]

Notice that you can solve either problem, so printing the cycle $2-4-3-1-5-6$ is also acceptable.

In the second sample:

[Image]

Notice that if there are multiple answers you can print any, so printing the cycle $2-5-6$, for example, is acceptable.

In the third sample:

$A$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are an architect and you have just been appointed to build a new swimming hall. The organisation behind these plans has acquired funding for a swimming pool and surrounding building as large as they want, but unfortunately they could not find anyone willing to pay for the floor surrounding the pool. They decided to pay for the floor tiles out of their own pocket. Because this has already cost them an arm and a leg, they want you to use all the floor tiles in your proposed plan.

Being an architect, you care for aesthetics. You see it as absolutely vital that both the swimming pool and the surrounding building are perfect squares. This raises an interesting problem: how can you make sure that the square shapes are guaranteed, while still using all the floor tiles the organisation bought?

Given the number of tiles $n$, find the length of the side of the building $m$ and and the length of the side of the pool $k$ such that $n=m^2-k^2$, or print impossible if no suitable $m$ and $k$ exist.

-----Input-----
 - One line containing a single integer $1\leq n\leq 10^9$.

-----Output-----
Print two non-negative integers $m$, $k$ such that $n = m^2 - k^2$, or print impossible if no such integers exist. If there are multiple valid solutions, you may output any one of them.

-----Examples-----
Sample Input 1:
7
Sample Output 1:
4 3

Sample Input 2:
10
Sample Output 2:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi loves walking on a tree. The tree where Takahashi walks has N vertices numbered 1 through N. The i-th of the N-1 edges connects Vertex a_i and Vertex b_i.

Takahashi has scheduled M walks. The i-th walk is done as follows:

* The walk involves two vertices u_i and v_i that are fixed beforehand.
* Takahashi will walk from u_i to v_i or from v_i to u_i along the shortest path.



The happiness gained from the i-th walk is defined as follows:

* The happiness gained is the number of the edges traversed during the i-th walk that satisfies one of the following conditions:
* In the previous walks, the edge has never been traversed.
* In the previous walks, the edge has only been traversed in the direction opposite to the direction taken in the i-th walk.



Takahashi would like to decide the direction of each walk so that the total happiness gained from the M walks is maximized. Find the maximum total happiness that can be gained, and one specific way to choose the directions of the walks that maximizes the total happiness.

Constraints

* 1 ≤ N,M ≤ 2000
* 1 ≤ a_i , b_i ≤ N
* 1 ≤ u_i , v_i ≤ N
* a_i \neq b_i
* u_i \neq v_i
* The graph given as input is a tree.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1
:
a_{N-1} b_{N-1}
u_1 v_1
:
u_M v_M


Output

Print the maximum total happiness T that can be gained, and one specific way to choose the directions of the walks that maximizes the total happiness, in the following format:


T
u^'_1 v^'_1
:
u^'_M v^'_M


where (u^'_i,v^'_i) is either (u_i,v_i) or (v_i,u_i), which means that the i-th walk is from vertex u^'_i to v^'_i.

Examples

Input

4 3
2 1
3 1
4 1
2 3
3 4
4 2


Output

6
2 3
3 4
4 2


Input

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


Output

6
2 4
3 5
5 1


Input

6 4
1 2
2 3
1 4
4 5
4 6
2 4
3 6
5 6
4 5


Output

9
2 4
6 3
5 6
4 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Same as [the original](https://www.codewars.com/kata/simple-fun-number-258-is-divisible-by-6) (same rules, really, go there for example and I strongly recommend completing it first), but with more than one asterisk (but always at least one).

For example, `"*2"` should return `["12", "42", "72"]`.

Similarly, `"*2*"` should return `["024", "120", "126", "222", "228", "324", "420", "426", "522", "528", "624", "720", "726", "822", "828", "924"]`. Order matters and returning the right one is part of the challenge itself, yep!

More examples in the test codes and, of course, if you cannot generate any number divisible by 6, just return `[]` (or `[] of String` in Crystal).

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