vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Fox And Snake

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fox Ciel starts to learn programming. The first task is drawing a fox! However, that turns out to be too hard for a beginner, so she decides to draw a snake instead.

A snake is a pattern on a *n* by *m* table. Denote *c*-th cell of *r*-th row as (*r*,<=*c*). The tail of the snake is located at (1,<=1), then it's body extends to (1,<=*m*), then goes down 2 rows to (3,<=*m*), then goes left to (3,<=1) and so on.

Your task is to draw this snake for Fox Ciel: the empty cells should be represented as dot characters ('.') and the snake cells should be filled with number signs ('#').

Consider sample tests in order to understand the snake pattern.

Input Specification:
The only line contains two integers: *n* and *m* (3<=≤<=*n*,<=*m*<=≤<=50). 

*n* is an odd number.

Output Specification:
Output *n* lines. Each line should contain a string consisting of *m* characters. Do not output spaces.

Demo Input:
['3 3\n', '3 4\n', '5 3\n', '9 9\n']

Demo Output:
['###\n..#\n###\n', '####\n...#\n####\n', '###\n..#\n###\n#..\n###\n', '#########\n........#\n#########\n#........\n#########\n........#\n#########\n#........\n#########\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Eric is the teacher of graph theory class. Today, Eric teaches independent set and edge-induced subgraph.

Given a graph $G=(V,E)$, an independent set is a subset of vertices $V' \subset V$ such that for every pair $u,v \in V'$, $(u,v) \not \in E$ (i.e. no edge in $E$ connects two vertices from $V'$).

An edge-induced subgraph consists of a subset of edges $E' \subset E$ and all the vertices in the original graph that are incident on at least one edge in the subgraph.

Given $E' \subset E$, denote $G[E']$ the edge-induced subgraph such that $E'$ is the edge set of the subgraph. Here is an illustration of those definitions: [Image] 

In order to help his students get familiar with those definitions, he leaves the following problem as an exercise:

Given a tree $G=(V,E)$, calculate the sum of $w(H)$ over all except null edge-induced subgraph $H$ of $G$, where $w(H)$ is the number of independent sets in $H$. Formally, calculate $\sum \limits_{\emptyset \not= E' \subset E} w(G[E'])$.

Show Eric that you are smarter than his students by providing the correct answer as quickly as possible. Note that the answer might be large, you should output the answer modulo $998,244,353$.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$), representing the number of vertices of the graph $G$.

Each of the following $n-1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$, $u \not= v$), describing edges of the given tree.

It is guaranteed that the given edges form a tree.


-----Output-----

Output one integer, representing the desired value modulo $998,244,353$.


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

Output
3

Input
3
1 2
3 2

Output
11



-----Note-----

For the second example, all independent sets are listed below. $\vdots : \vdots : \vdots$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Convenient For Everybody

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
In distant future on Earth day lasts for *n* hours and that's why there are *n* timezones. Local times in adjacent timezones differ by one hour. For describing local time, hours numbers from 1 to *n* are used, i.e. there is no time "0 hours", instead of it "*n* hours" is used. When local time in the 1-st timezone is 1 hour, local time in the *i*-th timezone is *i* hours.

Some online programming contests platform wants to conduct a contest that lasts for an hour in such a way that its beginning coincides with beginning of some hour (in all time zones). The platform knows, that there are *a**i* people from *i*-th timezone who want to participate in the contest. Each person will participate if and only if the contest starts no earlier than *s* hours 00 minutes local time and ends not later than *f* hours 00 minutes local time. Values *s* and *f* are equal for all time zones. If the contest starts at *f* hours 00 minutes local time, the person won't participate in it.

Help platform select such an hour, that the number of people who will participate in the contest is maximum.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=100<=000) — the number of hours in day.

The second line contains *n* space-separated integers *a*1, *a*2, ..., *a**n* (1<=≤<=*a**i*<=≤<=10<=000), where *a**i* is the number of people in the *i*-th timezone who want to participate in the contest.

The third line contains two space-separated integers *s* and *f* (1<=≤<=*s*<=&lt;<=*f*<=≤<=*n*).

Output Specification:
Output a single integer — the time of the beginning of the contest (in the first timezone local time), such that the number of participants will be maximum possible. If there are many answers, output the smallest among them.

Demo Input:
['3\n1 2 3\n1 3\n', '5\n1 2 3 4 1\n1 3\n']

Demo Output:
['3\n', '4\n']

Note:
In the first example, it's optimal to start competition at 3 hours (in first timezone). In this case, it will be 1 hour in the second timezone and 2 hours in the third timezone. Only one person from the first timezone won't participate.

In second example only people from the third and the fourth timezones will participate.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s$. You can build new string $p$ from $s$ using the following operation no more than two times:   choose any subsequence $s_{i_1}, s_{i_2}, \dots, s_{i_k}$ where $1 \le i_1 < i_2 < \dots < i_k \le |s|$;  erase the chosen subsequence from $s$ ($s$ can become empty);  concatenate chosen subsequence to the right of the string $p$ (in other words, $p = p + s_{i_1}s_{i_2}\dots s_{i_k}$). 

Of course, initially the string $p$ is empty. 

For example, let $s = \text{ababcd}$. At first, let's choose subsequence $s_1 s_4 s_5 = \text{abc}$ — we will get $s = \text{bad}$ and $p = \text{abc}$. At second, let's choose $s_1 s_2 = \text{ba}$ — we will get $s = \text{d}$ and $p = \text{abcba}$. So we can build $\text{abcba}$ from $\text{ababcd}$.

Can you build a given string $t$ using the algorithm above?


-----Input-----

The first line contains the single integer $T$ ($1 \le T \le 100$) — the number of test cases.

Next $2T$ lines contain test cases — two per test case. The first line contains string $s$ consisting of lowercase Latin letters ($1 \le |s| \le 400$) — the initial string.

The second line contains string $t$ consisting of lowercase Latin letters ($1 \le |t| \le |s|$) — the string you'd like to build.

It's guaranteed that the total length of strings $s$ doesn't exceed $400$.


-----Output-----

Print $T$ answers — one per test case. Print YES (case insensitive) if it's possible to build $t$ and NO (case insensitive) otherwise.


-----Example-----
Input
4
ababcd
abcba
a
b
defi
fed
xyz
x

Output
YES
NO
NO
YES

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day Polycarpus stopped by a supermarket on his way home. It turns out that the supermarket is having a special offer for stools. The offer is as follows: if a customer's shopping cart contains at least one stool, the customer gets a 50% discount on the cheapest item in the cart (that is, it becomes two times cheaper). If there are several items with the same minimum price, the discount is available for only one of them!

Polycarpus has *k* carts, and he wants to buy up all stools and pencils from the supermarket. Help him distribute the stools and the pencils among the shopping carts, so that the items' total price (including the discounts) is the least possible.

Polycarpus must use all *k* carts to purchase the items, no shopping cart can remain empty. Each shopping cart can contain an arbitrary number of stools and/or pencils.

Input Specification:
The first input line contains two integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=103) — the number of items in the supermarket and the number of carts, correspondingly. Next *n* lines describe the items as "*c**i* *t**i*" (without the quotes), where *c**i* (1<=≤<=*c**i*<=≤<=109) is an integer denoting the price of the *i*-th item, *t**i* (1<=≤<=*t**i*<=≤<=2) is an integer representing the type of item *i* (1 for a stool and 2 for a pencil). The numbers in the lines are separated by single spaces.

Output Specification:
In the first line print a single real number with exactly one  decimal place — the minimum total price of the items, including the discounts.

In the following *k* lines print the descriptions of the items in the carts. In the *i*-th line print the description of the *i*-th cart as "*t* *b*1 *b*2 ... *b**t*" (without the quotes), where *t* is the number of items in the *i*-th cart, and the sequence *b*1,<=*b*2,<=...,<=*b**t* (1<=≤<=*b**j*<=≤<=*n*) gives the indices of items to put in this cart in the optimal distribution. All indices of items in all carts should be pairwise different, each item must belong to exactly one cart. You can print the items in carts and the carts themselves in any order. The items are numbered from 1 to *n* in the order in which they are specified in the input.

If there are multiple optimal distributions, you are allowed to print any of them.

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

Demo Output:
['5.5\n2 1 2\n1 3\n', '8.0\n1 1\n2 4 2\n1 3\n']

Note:
In the first sample case the first cart should contain the 1st and 2nd items, and the second cart should contain the 3rd item. This way each cart has a stool and each cart has a 50% discount for the cheapest item. The total price of all items will be: 2·0.5 + (3 + 3·0.5) = 1 + 4.5 = 5.5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems: <https://codeforces.com/blog/entry/45307>.

The jury guessed some array a consisting of 6 integers. There are 6 special numbers — 4, 8, 15, 16, 23, 42 — and each of these numbers occurs in a exactly once (so, a is some permutation of these numbers).

You don't know anything about their order, but you are allowed to ask up to 4 queries. In each query, you may choose two indices i and j (1 ≤ i, j ≤ 6, i and j are not necessarily distinct), and you will get the value of a_i ⋅ a_j in return.

Can you guess the array a?

The array a is fixed beforehand in each test, the interaction program doesn't try to adapt to your queries.

Interaction

Before submitting the answer, you may ask up to 4 queries. To ask a query, print one line in the following format: ? i j, where i and j should be two integers such that 1 ≤ i, j ≤ 6. The line should be ended with a line break character. After submitting a query, flush the output and read the answer to your query — one line containing one integer a_i ⋅ a_j. If you submit an incorrect query (or ask more than 4 queries), the answer to it will be one string 0. After receiving such an answer, your program should terminate immediately — otherwise you may receive verdict "Runtime error", "Time limit exceeded" or some other verdict instead of "Wrong answer".

To give the answer, your program should print one line ! a_1 a_2 a_3 a_4 a_5 a_6 with a line break in the end. After that, it should flush the output and terminate gracefully.

Example

Input


16
64
345
672

Output


? 1 1
? 2 2
? 3 5
? 4 6
! 4 8 15 16 23 42

Note

If you want to submit a hack for this problem, your test should contain exactly six space-separated integers a_1, a_2, ..., a_6. Each of 6 special numbers should occur exactly once in the test. The test should be ended with a line break character.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a simple game you must have played around with during your school days, calculating FLAMES of you and your crush! Given the names of two people, cancel out the common letters (repeated occurrence of a letter is treated separately, so 2A's in one name and one A in the other would cancel one A in each name), count the total number of remaining letters (n) and repeatedly cut the letter in the word FLAMES which hits at the nth number when we count from F in cyclic manner.

For example:
NAME 1: SHILPA
NAME 2: AAMIR
After cutting the common letters: 
NAME 1: SHILPA 
NAME 2: AAMIR
Total number of letters left=7
FLAMES, start counting from F : 1=F, 2=L, 3=A, 4=M, 5=E, 6=S,7=F...So cut F
FLAMES: repeat this process with remaining letters of FLAMES for number 7 (start count from the letter after 
the last letter cut) . In the end, one letter remains. Print the result corresponding to the last letter:
F=FRIENDS
L=LOVE
A=ADORE
M=MARRIAGE
E=ENEMIES
S=SISTER

-----Input-----
The no. of test cases (<100)
two names (may include spaces) for each test case.


-----Output-----
FLAMES result (Friends/Love/...etc) for each test case

-----Example-----
Input:
2
SHILPA
AAMIR
MATT
DENISE

Output:
ENEMIES
LOVE



By:
Chintan, Asad, Ashayam, Akanksha

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is playing a game on the non-negative x-axis. It takes him $1$ second to reach from $i^{th}$ position to $(i-1)^{th}$ position or $(i+1)^{th}$ position. The chef never goes to the negative x-axis. Also, Chef doesn't stop at any moment of time.
The movement of chef can be described as follows.
- At the start he is standing at $x=0$ at time $0$.
- In the first round, he moves towards $x=1$ and comes back to the $x=0$ position. 
- In the second round, he moves towards the $x=2$ and comes back again to $x=0$. 
- Generalizing, in the $k^{th}$ round, he moves from $x=0$ to $x=k$ and then returns back to $x=0$ at the end of the round. This goes on as the game progresses.
For Example, the path of Chef for $3^{rd}$ round is given below.
$0 - 1 - 2 - 3 - 2 - 1 - 0$ 
The overall path followed by Chef would look somewhat like this:
$0 - 1 - 0 - 1 - 2 - 1 - 0 - 1 - 2 - 3 - 2 - 1 - 0 - 1 - 2 - 3 - 4 - 3 - …$
You are given two non-negative integers $N$ and $K$. You have to tell the time at which Chef arrives at $x=N$ for the $K^{th}$ time. 
Note - Chef can not skip a position while visiting the positions.

-----Input:-----
- The first line contains $T$ the number of test cases. Then the test cases follow.
- Each test case contains a single line of two integers $N$ and $K$.

-----Output:-----
For each test case, print a single line containing one integer -- the time taken by the chef to arrive at $x=N$ for the $K^{th}$ time by modulo $1,000,000,007$.

-----Constraints-----
- $1 \le T \le 10^5$
- $0 \le N \le 10^9$
- $1 \le K \le 10^9$

-----Sample Input:-----
5
0 1
1 1
2 1
1 3
4 6

-----Sample Output:-----
0
1
4
5
46

-----Explanation:-----
Test Case 1:

Chef starts the journey from the $N = 0$ at time $t = 0$ and it's the first time $(K = 1)$, he is here. So, the answer is $0$.  
Test Case 2:

Chef starts the journey from the $N = 0$ at time $t = 0$ then goes to $N = 1$ at $t = 1$ and it's the first time $(K = 1)$, he is here. So, the answer is $1$.
Test Case 4:

The path followed by Chef to reach $1$ for the third time is given below.
$0 - 1 - 0 - 1 - 2 - 1$

He reaches $1$ for the third time at $t=5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:


Input: [1,3,5]
Output: 1

Example 2:


Input: [2,2,2,0,1]
Output: 0

Note:


       This is a follow up problem to Find Minimum in Rotated Sorted Array.
       Would allow duplicates affect the run-time complexity? How and why?

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A country Gizevom is being under a sneak and fierce attack by their foe. They have to deploy one or more troops to every base immediately in order to defend their country. Otherwise their foe would take all the bases and declare "All your base are belong to us."

You are asked to write a program that calculates the minimum time required for deployment, given the present positions and marching speeds of troops and the positions of the bases.



Input

The input consists of multiple datasets. Each dataset has the following format:

N M
x1 y1 v1
x2 y2 v2
...
xN yN vN
x'1 y'1
x'2 y'2
...
x'M y'M


N is the number of troops (1 ≤ N ≤ 100); M is the number of bases (1 ≤ M ≤ 100); (xi, yi ) denotes the present position of i-th troop; vi is the speed of the i-th troop (1 ≤ vi ≤ 100); (x'j, y'j) is the position of the j-th base.

All the coordinates are integers between 0 and 10000 inclusive.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the minimum required time in a line.

Example

Input

2 2
10 20 1
0 10 1
0 10
10 0
0 0


Output

14.14213562

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rohit collects coins: he has exactly one coin for every year from 1 to n. Naturally, Rohit keeps all the coins in his collection in the order in which they were released. Once Rohit's younger brother made a change — he took all the coins whose release year dated from l to r inclusively and put them in the reverse order. That is, he took a certain segment [l, r] and reversed it. At that, the segment's endpoints did not coincide. For example, if n = 8, then initially Rohit's coins were kept in the order 1 2 3 4 5 6 7 8. If Rohit's younger brother chose the segment [2, 6], then after the reversal the coin order will change to 1 6 5 4 3 2 7 8. Rohit suspects that someone else could have spoilt the permutation after his brother. Help him to find that out. Check if the given permutation can be obtained from the permutation 1 2 … n using exactly one segment reversal. If it is possible, find the segment itself.

-----Input:-----
- The first line contains an integer N which is the number of coins in Rohit's collection. 
- The second line contains space-separated n integers which are the spoilt sequence of coins. It is guaranteed that the given sequence is a permutation, i.e. it contains only integers from 1 to n, and every number is used exactly 1 time.

-----Output:-----
If it is impossible to obtain the given permutation from the original one in exactly one action, print 0 0. Otherwise, print two numbers l, r (1 ≤ l < r ≤ n) which are the endpoints of the segment that needs to be reversed to obtain from permutation 1 2 … n the given one.

-----Constraints-----
- $1 \leq N \leq 1000$
- $1 \leq A[N] \leq 10^9$

-----Sample Input:-----
8
1 6 5 4 3 2 7 8

-----Sample Output:-----
2 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Teams Formation

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
This time the Berland Team Olympiad in Informatics is held in a remote city that can only be reached by one small bus. Bus has *n* passenger seats, seat *i* can be occupied only by a participant from the city *a**i*.

Today the bus has completed *m* trips, each time bringing *n* participants. The participants were then aligned in one line in the order they arrived, with people from the same bus standing in the order of their seats (i. e. if we write down the cities where the participants came from, we get the sequence *a*1,<=*a*2,<=...,<=*a**n* repeated *m* times).

After that some teams were formed, each consisting of *k* participants form the same city standing next to each other in the line. Once formed, teams left the line. The teams were formed until there were no *k* neighboring participants from the same city.

Help the organizers determine how many participants have left in the line after that process ended. We can prove that answer doesn't depend on the order in which teams were selected.

Input Specification:
The first line contains three integers *n*,<=*k* and *m* (1<=≤<=*n*<=≤<=105, 2<=≤<=*k*<=≤<=109, 1<=≤<=*m*<=≤<=109).

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=105), where *a**i* is the number of city, person from which must take seat *i* in the bus.

Output Specification:
Output the number of remaining participants in the line.

Demo Input:
['4 2 5\n1 2 3 1\n', '1 9 10\n1\n', '3 2 10\n1 2 1\n']

Demo Output:
['12\n', '1\n', '0\n']

Note:
In the second example, the line consists of ten participants from the same city. Nine of them will form a team. At the end, only one participant will stay in the line.

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

Zark is a novice coder, who is obsessed with sequential problems. One fine day,
 Zark's friend King gave him a sequence of integers and asked him to write a
code to find the minimum number of changes required to make the sequence strictly increasing (consisting of positive integers only).

Your task is to help Zark find out the minimum number of changes.

Note: You can replace any number with a positive integer.

INPUT SPECIFICATION:

You will be given 't' test cases, each test case will consist of a number 'n' denoting the

length of sequence (no. of elements in sequence). The next line will consist of array of

elements 'a[i]' of the given sequence.

CONSTRAINTS:

n < 10^6

a[i] < 10^9

OUTPUT SPECIFICATION:

The output for each test case will consist of single line denoting the minimum number of changes required.

SAMPLE INPUT
6
7 4 5 9 0 11

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.
Return the element repeated N times.
 



Example 1:
Input: [1,2,3,3]
Output: 3


Example 2:
Input: [2,1,2,5,3,2]
Output: 2


Example 3:
Input: [5,1,5,2,5,3,5,4]
Output: 5

 
Note:

4 <= A.length <= 10000
0 <= A[i] < 10000
A.length is even

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a table on which N balls are kept starting from index 1 to N in horizontal direction. Each ball is either of  red (denoted by 'R') or of blue (denoted by 'B') color. Any red ball which is placed on even indices and blue balls placed on odd indices is considered as wrongly placed. You need return the number of balls placed wrong on the table.
 
Example 1:
Input:
S = "RRBB"
Output: 2
Explanation: second R and first B
is wrongly placed.
Ã¢â¬â¹
Example 2:
Input: 
S = "RBRB"
Output: 0
Explanation: No ball is wrongly placed.
Your Task:
You don't need to read input or print anything. Your task is to complete the function countWrongPlacedBalls() which accpets a string as input parameter and returns the number of wrongly placed balls.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1<= N <=10^{5}
S[i] = 'R' or S[i] = 'B'

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