vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Scheduling is how the processor decides which jobs(processes) get to use the processor and for how long. This can cause a lot of problems. Like a really long process taking the entire CPU and freezing all the other processes. One solution is Shortest Job First(SJF), which today you will be implementing.

SJF works by, well, letting the shortest jobs take the CPU first. If the jobs are the same size then it is First In First Out (FIFO). The idea is that the shorter jobs will finish quicker, so theoretically jobs won't get frozen because of large jobs. (In practice they're frozen because of small jobs).

You will be implementing:
```python
  def SJF(jobs, index)
```

It takes in:

1. "jobs" a non-empty array of positive integers. They represent the clock-cycles(cc) needed to finish the job.
2. "index" a positive integer. That represents the job we're interested in.

SJF returns:

1. A positive integer representing the cc it takes to complete the job at index.

Here's an example:
```
SJF([3, 10, 20, 1, 2], 0)
at 0cc [3, 10, 20, 1, 2] jobs[3] starts
at 1cc [3, 10, 20, 0, 2] jobs[3] finishes, jobs[4] starts
at 3cc [3, 10, 20, 0, 0] jobs[4] finishes, jobs[0] starts
at 6cc [0, 10, 20, 0, 0] jobs[0] finishes
```

so:
```
SJF([3,10,20,1,2], 0) == 6
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Function Descriptions=====
.difference()

The tool .difference() returns a set with all the elements from the set that are not in an iterable.
Sometimes the - operator is used in place of the .difference() tool, but it only operates on the set of elements in set.
Set is immutable to the .difference() operation (or the - operation).

>>> s = set("Hacker")
>>> print s.difference("Rank")
set(['c', 'r', 'e', 'H'])

>>> print s.difference(set(['R', 'a', 'n', 'k']))
set(['c', 'r', 'e', 'H'])

>>> print s.difference(['R', 'a', 'n', 'k'])
set(['c', 'r', 'e', 'H'])

>>> print s.difference(enumerate(['R', 'a', 'n', 'k']))
set(['a', 'c', 'r', 'e', 'H', 'k'])

>>> print s.difference({"Rank":1})
set(['a', 'c', 'e', 'H', 'k', 'r'])

>>> s - set("Rank")
set(['H', 'c', 'r', 'e'])

=====Problem Statement=====
Students of District College have a subscription to English and French newspapers. Some students have subscribed to only the English newspaper, some have subscribed to only the French newspaper, and some have subscribed to both newspapers.

You are given two sets of student roll numbers. One set has subscribed to the English newspaper, and one set has subscribed to the French newspaper. Your task is to find the total number of students who have subscribed to only English newspapers.

=====Input Format=====
The first line contains the number of students who have subscribed to the English newspaper.
The second line contains the space separated list of student roll numbers who have subscribed to the English newspaper.
The third line contains the number of students who have subscribed to the French newspaper.
The fourth line contains the space separated list of student roll numbers who have subscribed to the French newspaper.

=====Constraints=====
0<Total number of students in college<1000

=====Output Format=====
Output the total number of students who are subscribed to the English newspaper only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In "Takahashi-ya", a ramen restaurant, basically they have one menu: "ramen", but N kinds of toppings are also offered. When a customer orders a bowl of ramen, for each kind of topping, he/she can choose whether to put it on top of his/her ramen or not. There is no limit on the number of toppings, and it is allowed to have all kinds of toppings or no topping at all. That is, considering the combination of the toppings, 2^N types of ramen can be ordered.
Akaki entered Takahashi-ya. She is thinking of ordering some bowls of ramen that satisfy both of the following two conditions:
 - Do not order multiple bowls of ramen with the exactly same set of toppings.
 - Each of the N kinds of toppings is on two or more bowls of ramen ordered.
You are given N and a prime number M. Find the number of the sets of bowls of ramen that satisfy these conditions, disregarding order, modulo M. Since she is in extreme hunger, ordering any number of bowls of ramen is fine.

-----Constraints-----
 - 2 \leq N \leq 3000
 - 10^8 \leq M \leq 10^9 + 9
 - N is an integer.
 - M is a prime number.

-----Subscores-----
 - 600 points will be awarded for passing the test set satisfying N ≤ 50.

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

-----Output-----
Print the number of the sets of bowls of ramen that satisfy the conditions, disregarding order, modulo M.

-----Sample Input-----
2 1000000007

-----Sample Output-----
2

Let the two kinds of toppings be A and B. Four types of ramen can be ordered: "no toppings", "with A", "with B" and "with A, B". There are two sets of ramen that satisfy the conditions:
 - The following three ramen: "with A", "with B", "with A, B".
 - Four ramen, one for each type.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Peter is expecting a large shipment of fuel oil, but he has a small problem (doesn’t everyone in these programming problems!). The only containers he has are a set of large bottles (each with the same volume) and a set of smaller bottles (also each with the same, but smaller volume). Given the volume of the shipment of oil, he would like to store the oil in the bottles so that
 - all of the oil is stored,
 - each bottle is filled to the top, and
 - the minimum number of bottles is used.

While Peter thinks he has solved this problem for his given bottle sizes, he often spends hours wondering what would happen if his bottles had different volumes (apparently Peter doesn’t lead the most exciting life).

-----Input-----
The input consists of a single line containing three positive integers $s$$v_1$ $v_2$, where $s \leq 10^6$ is the volume of the shipment, and $v_1, v_2 \leq 10^6$ are the volumes of the two types of bottles, with $v_1 > v_2$.

-----Output-----
Output the number of bottles of size $v_1$ and the number of bottles of size $v_2$ which satisfy Peter’s two conditions. If the conditions cannot be met, output Impossible.

-----Examples-----
Sample Input 1:
1000 9 7
Sample Output 1:
108 4

Sample Input 2:
1000 900 7
Sample Output 2:
Impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi is playing a board game called Sugoroku.
On the board, there are N + 1 squares numbered 0 to N. Takahashi starts at Square 0, and he has to stop exactly at Square N to win the game.
The game uses a roulette with the M numbers from 1 to M. In each turn, Takahashi spins the roulette. If the number x comes up when he is at Square s, he moves to Square s+x. If this makes him go beyond Square N, he loses the game.
Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string S of length N + 1, representing which squares are Game Over Squares. For each i (0 \leq i \leq N), Square i is a Game Over Square if S[i] = 1 and not if S[i] = 0.
Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print -1.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - 1 \leq M \leq 10^5
 - |S| = N + 1
 - S consists of 0 and 1.
 - S[0] = 0
 - S[N] = 0

-----Input-----
Input is given from Standard Input in the following format:
N M
S

-----Output-----
If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.
If Takahashi cannot win the game, print -1.

-----Sample Input-----
9 3
0001000100

-----Sample Output-----
1 3 2 3

If the numbers 1, 3, 2, 3 come up in this order, Takahashi can reach Square 9 via Square 1, 4, and 6. He cannot reach Square 9 in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square 9 in four turns.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has 2 numbers A and B (A < B).

Chef will perform some operations on A. 

In the i^{th} operation:
Chef will add 1 to A if i is odd.
Chef will add 2 to A if i is even.

Chef can stop at any instant. Can Chef make A equal to B?

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space separated integers A and B.

------ Output Format ------ 

For each test case, output YES if Chef can make A and B equal, NO otherwise.

Note that the checker is case-insensitive. So, YES, Yes, yEs are all considered same.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ A < B ≤ 10^{9}$

----- Sample Input 1 ------ 
4
1 2
3 6
4 9
10 20

----- Sample Output 1 ------ 
YES
YES
NO
YES

----- explanation 1 ------ 
Test case 1: Chef may perform one operation to make $A$ equal to $B$: $1 \xrightarrow{+1} 2$

Test case 2: $3 \xrightarrow{+1} 4 \xrightarrow{+2} 6$

Test case 3: It can be shown that it is impossible to make $A$ and $B$ equal.

Test case 4: $10 \xrightarrow{+1} 11 \xrightarrow{+2} 13 \xrightarrow{+1} 14 \xrightarrow{+2} 16 \xrightarrow{+1} 17 \xrightarrow{+2} 19 \xrightarrow{+1} 20$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N light bulbs are connected by a wire. Each bulb has a switch associated with it, however due to faulty wiring, a switch also changes the state of all the bulbs to the right of current bulb. Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs. "0 represents the bulb is off and 1 represents the bulb is on."
 
Example 1:
Input:
N=4
arr[] = { 0, 0, 0, 0 }
Output:  1
Explanation: 
From the given set of bulbs change
the state of the first bulb from off
to on ,which eventually turn the rest
three bulbs on the right of it.
Example 2:
Input:
N=4
arr[] = { 1, 0, 0, 1 }
Output:  2
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function countFlips() that takes array A and integer N as parameters and returns the minimum number of press required to turn on all the bulbs.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a two-dimensional list in the following format:

```python
data = [[2, 5], [3, 4], [8, 7]]
```

Each sub-list contains two items, and each item in the sub-lists is an integer.

Write a function `process_data()` that processes each sub-list like so:

 * `[2, 5]` --> `2 - 5` --> `-3`
 * `[3, 4]` --> `3 - 4` --> `-1`
 * `[8, 7]` --> `8 - 7` --> `1`
 
and then returns the product of all the processed sub-lists: `-3 * -1 * 1` --> `3`.

For input, you can trust that neither the main list nor the sublists will be empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number s in their binary representation. Return the number of steps to reduce it to 1 under the following rules:


If the current number is even, you have to divide it by 2.


If the current number is odd, you have to add 1 to it.


It's guaranteed that you can always reach to one for all testcases.
 
Example 1:
Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

Example 2:
Input: s = "10"
Output: 1
Explanation: "10" corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.  

Example 3:
Input: s = "1"
Output: 0

 
Constraints:

1 <= s.length <= 500
s consists of characters '0' or '1'
s[0] == '1'

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.
Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.
A subarray is defined as a contiguous block of elements in the array.
 
Example 1:
Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

Example 2:
Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

Example 3:
Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

Example 4:
Input: nums = [1,2,3], p = 7
Output: -1
Explanation: There is no way to remove a subarray in order to get a sum divisible by 7.

Example 5:
Input: nums = [1000000000,1000000000,1000000000], p = 3
Output: 0

 
Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= p <= 109

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bizon the Champion isn't just friendly, he also is a rigorous coder.

Let's define function f(a), where a is a sequence of integers. Function f(a) returns the following sequence: first all divisors of a1 go in the increasing order, then all divisors of a2 go in the increasing order, and so on till the last element of sequence a. For example, f([2, 9, 1]) = [1, 2, 1, 3, 9, 1].

Let's determine the sequence Xi, for integer i (i ≥ 0): X0 = [X] ([X] is a sequence consisting of a single number X), Xi = f(Xi - 1) (i > 0). For example, at X = 6 we get X0 = [6], X1 = [1, 2, 3, 6], X2 = [1, 1, 2, 1, 3, 1, 2, 3, 6].

Given the numbers X and k, find the sequence Xk. As the answer can be rather large, find only the first 105 elements of this sequence.

Input

A single line contains two space-separated integers — X (1 ≤ X ≤ 1012) and k (0 ≤ k ≤ 1018).

Output

Print the elements of the sequence Xk in a single line, separated by a space. If the number of elements exceeds 105, then print only the first 105 elements.

Examples

Input

6 1


Output

1 2 3 6 


Input

4 2


Output

1 1 2 1 2 4 


Input

10 3


Output

1 1 1 2 1 1 5 1 1 2 1 5 1 2 5 10 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Yraglac has just finished building a robot! It’s fancy: two wheels, with an auto-balancing system, several cameras, wireless connectivity, and a sattelite dish. There’s just one little problem…

He powered it up, sent it off for a test, and now it’s not responding to any inputs. All he has is a photograph of the floor below it, acquired during an attempted rendition of Robot Ballet. Yraglac wasn’t really paying attention to where it was, though, as he was too excited.

Thankfully, one of Yraglac’s classmates has produced a huge stitched-together image of all of the floors in the University. Now all Yraglac has to do is figure out where this image of the floor is, and then he can just go and pick up the robot directly.

Unfortunately, Yraglac doesn’t have the patience to look through the entire huge image for anything that matches, so he wants to write a program that will find an initial set of locations that seem like candidates.

Thankfully, due to …cough …the fact that this is a competitive programming problem …cough …the images are of exactly the same scale, so Yraglac should be able to figure out where the robot is simply by checking how closely the robot’s image matches the floor image at each possible place to overlay the robot’s image on the floor image.

Yraglac will consider a location as a candidate if it is tied for having the most number of pixels the same between the two images.

-----Input-----
The input consists of two images, the first of which is the last image seen from the robot, and the second is the entire floor of the university.

Each image begins with a line consisting of two integers, $W$ and $H$, the width and height, respectively. You may assume that $W, H \leq 1000$, and that the floor image is at least as large as the robot’s image.

Following on the next $H$ lines are $W$ space-separated integers, either 0 or 1, denoting the colour at the given pixel.

-----Output-----
The output should consist of at least one line, one each for a candidate location, each containing a coordinate $(x,y)$ as two numbers separated by a single space, with $x$ first and $y$ second. The coordinates should be sorted by x-coordinate, and then by y-coordinate.

-----Examples-----
Sample Input:
2 2
1 0
0 1
3 3
1 0 0
0 1 0
0 0 1
Sample Output:
0 0
1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"The Shell Game" involves cups upturned on a playing surface, with a ball placed underneath one of them.  The index of the cups are swapped around multiple times. After that the players will try to find which cup contains the ball.

Your task is as follows.  Given the cup that the ball starts under, and list of swaps, return the location of the ball at the end.  Cups are given like array/list indices.

For example, given the starting position `0` and the swaps `[(0, 1), (1, 2), (1, 0)]`:

 * The first swap moves the ball from `0` to `1`
 * The second swap moves the ball from `1` to `2`
 * The final swap doesn't affect the position of the ball.
 
 So

```python
find_the_ball(0, [(0, 1), (2, 1), (0, 1)]) == 2
```

There aren't necessarily only three cups in this game, but there will be at least two.  You can assume all swaps are valid, and involve two distinct indices.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp found the string $s$ and the permutation $p$. Their lengths turned out to be the same and equal to $n$.

A permutation of $n$ elements — is an array of length $n$, in which every integer from $1$ to $n$ occurs exactly once. For example, $[1, 2, 3]$ and $[4, 3, 5, 1, 2]$ are permutations, but $[1, 2, 4]$, $[4, 3, 2, 1, 2]$ and $[0, 1, 2]$ are not.

In one operation he can multiply $s$ by $p$, so he replaces $s$ with string $new$, in which for any $i$ from $1$ to $n$ it is true that $new_i = s_{p_i}$. For example, with $s=wmbe$ and $p = [3, 1, 4, 2]$, after operation the string will turn to $s=s_3 s_1 s_4 s_2=bwem$.

Polycarp wondered after how many operations the string would become equal to its initial value for the first time. Since it may take too long, he asks for your help in this matter.

It can be proved that the required number of operations always exists. It can be very large, so use a 64-bit integer type.


-----Input-----

The first line of input contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases in input.

The first line of each case contains single integer $n$ ($1 \le n \le 200$) — the length of string and permutation.

The second line of each case contains a string $s$ of length $n$, containing lowercase Latin letters.

The third line of each case contains $n$ integers — permutation $p$ ($1 \le p_i \le n$), all $p_i$ are different.


-----Output-----

Output $t$ lines, each of which contains the answer to the corresponding test case of input. As an answer output single integer — the minimum number of operations, after which the string $s$ will become the same as it was before operations.


-----Examples-----

Input
3
5
ababa
3 4 5 2 1
5
ababa
2 1 4 5 3
10
codeforces
8 6 1 7 5 2 9 3 10 4
Output
1
6
12


-----Note-----

In the first sample operation doesn't change the string, so it will become the same as it was after $1$ operations.

In the second sample the string will change as follows:

$s$ = babaa

$s$ = abaab

$s$ = baaba

$s$ = abbaa

$s$ = baaab

$s$ = ababa

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have decided to introduce an automatic ticket gate to the railway network of a certain country. One of the difficult issues to implement is determining whether a given ticket can move between designated stations. Each ticket has a boarding station and a getting-off station. With this ticket, you can not only "get on at the boarding station and get off at the getting off station", but you are also allowed to get on and off the train.

There are S stations on this rail network, of which Group R stations are adjacent and can be traversed in both directions without going through other stations. There is only one railroad track connecting adjacent stations. The distance between adjacent stations is the distance measured along this railroad track. There are multiple possible routes from one station to another, depending on the shape of the railway network, but the route with the shortest distance is called the shortest route. If there are multiple such routes, both are accepted as the shortest route.

You can move from station c to station d with a ticket for boarding station a and getting off station b if there is a route p that meets all of the following conditions.

* Route p is the shortest route from station a to station b.
* Route p is a route that starts from station a, goes through station c, then station d, and ends at station b. The section from station c to station d is the shortest route between these two stations.



You will be given route map and ticket information. Next, you will be given several pairs of start and end points, so write a program that determines whether you can move from the start point to the end point with that ticket.



input

The input consists of one dataset. Input data is given in the following format.


S R
u1 v1 w1
u2 v2 w2
::
uR vR wR
a b Q
c1 d1
::
cQ dQ


The numbers given on each line are separated by a single space.

The first line consists of two integers. S (2 ≤ S ≤ 100000) is the number of stations that appear on the railroad map, and R (1 ≤ R ≤ 200000) is the number of pairs of adjacent stations. The following R line is given information on the railroad tracks that directly connect adjacent stations. ui and vi (1 ≤ ui, vi ≤ S) indicate the station numbers at both ends of the i-th line. wi (1 ≤ wi ≤ 1000) is an integer representing the distance between these stations. However, numbers from 1 to S are assigned to each station without duplication, and ui ≠ vi.

The next line consists of three integers. The first two integers represent the ticket sections, where a is the boarding station and b is the getting-off station (1 ≤ a, b ≤ S). The third integer Q (1 ≤ Q ≤ 40000) indicates the number of questions. The question is given on the following Q line. ci and di (1 ≤ ci, di ≤ S) indicate the boarding and alighting stations of the i-th question. However, a ≠ b and ci ≠ di.

output

For each question, print Yes if you can move with the given ticket, or No if you can't.

Example

Input

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


Output

Yes
Yes
Yes
Yes
No
No

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