vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Vivek initially has an empty array $a$ and some integer constant $m$.

He performs the following algorithm:  Select a random integer $x$ uniformly in range from $1$ to $m$ and append it to the end of $a$.  Compute the greatest common divisor of integers in $a$.  In case it equals to $1$, break  Otherwise, return to step $1$. 

Find the expected length of $a$. It can be shown that it can be represented as $\frac{P}{Q}$ where $P$ and $Q$ are coprime integers and $Q\neq 0 \pmod{10^9+7}$. Print the value of $P \cdot Q^{-1} \pmod{10^9+7}$.


-----Input-----

The first and only line contains a single integer $m$ ($1 \leq m \leq 100000$).


-----Output-----

Print a single integer — the expected length of the array $a$ written as $P \cdot Q^{-1} \pmod{10^9+7}$.


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

Output
1

Input
2

Output
2

Input
4

Output
333333338



-----Note-----

In the first example, since Vivek can choose only integers from $1$ to $1$, he will have $a=[1]$ after the first append operation, and after that quit the algorithm. Hence the length of $a$ is always $1$, so its expected value is $1$ as well.

In the second example, Vivek each time will append either $1$ or $2$, so after finishing the algorithm he will end up having some number of $2$'s (possibly zero), and a single $1$ in the end. The expected length of the list is $1\cdot \frac{1}{2} + 2\cdot \frac{1}{2^2} + 3\cdot \frac{1}{2^3} + \ldots = 2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is Bubble Cup finals season and farmer Johnny Bubbles must harvest his bubbles. The bubbles are in a rectangular bubblefield formed of N x M square parcels divided into N rows and M columns. The parcel in i^{th} row and j^{th} column yields A_{i,j} bubbles.

Johnny Bubbles has available a very special self-driving bubble harvester that, once manually positioned at the beginning of a row or column, automatically harvests all the bubbles in that row or column. Once the harvester reaches the end of the row or column it stops and must be repositioned. The harvester can pass through any parcel any number of times, but it can collect bubbles from the parcel only once.

Johnny is very busy farmer, so he is available to manually position the harvester at most four times per day. Johnny is also impatient, so he wants to harvest as many bubbles as possible on the first day.

Please help Johnny to calculate what is the maximum number of bubbles he can collect on the first day.

Input

The first line contains two integers N and M (1 ≤ N, M ≤ N * M ≤ 10^{5}) - the bubblefield size.

Each of the next N lines contains M integers. The j^{th} element in the i^{th} line is A_{i,j} (0 ≤ a_{i,j} ≤ 10^{9}) — the yield of the parcel located in the i^{th} row and the j^{th} column.

Output

Output contains one integer number - maximum number of the bubbles Johnny can harvest on the first day.

Examples

Input


2 2
1 2
3 4


Output


10


Input


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


Output


80

Note

In the first example, farmer Johnny can harvest all the bubbles by positioning the harvester on the first and the second row.

In the second example, one way Johnny can harvest maximum number of bubbles is to position the harvester in the second row, the fourth row, the second column and the fourth column.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions are constraints on $n$ and $k$.

You are messaging in one of the popular social networks via your smartphone. Your smartphone can show at most $k$ most recent conversations with your friends. Initially, the screen is empty (i.e. the number of displayed conversations equals $0$).

Each conversation is between you and some of your friends. There is at most one conversation with any of your friends. So each conversation is uniquely defined by your friend.

You (suddenly!) have the ability to see the future. You know that during the day you will receive $n$ messages, the $i$-th message will be received from the friend with ID $id_i$ ($1 \le id_i \le 10^9$).

If you receive a message from $id_i$ in the conversation which is currently displayed on the smartphone then nothing happens: the conversations of the screen do not change and do not change their order, you read the message and continue waiting for new messages.

Otherwise (i.e. if there is no conversation with $id_i$ on the screen):

  Firstly, if the number of conversations displayed on the screen is $k$, the last conversation (which has the position $k$) is removed from the screen.  Now the number of conversations on the screen is guaranteed to be less than $k$ and the conversation with the friend $id_i$ is not displayed on the screen.  The conversation with the friend $id_i$ appears on the first (the topmost) position on the screen and all the other displayed conversations are shifted one position down. 

Your task is to find the list of conversations (in the order they are displayed on the screen) after processing all $n$ messages.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 2 \cdot 10^5)$ — the number of messages and the number of conversations your smartphone can show.

The second line of the input contains $n$ integers $id_1, id_2, \dots, id_n$ ($1 \le id_i \le 10^9$), where $id_i$ is the ID of the friend which sends you the $i$-th message.


-----Output-----

In the first line of the output print one integer $m$ ($1 \le m \le min(n, k)$) — the number of conversations shown after receiving all $n$ messages.

In the second line print $m$ integers $ids_1, ids_2, \dots, ids_m$, where $ids_i$ should be equal to the ID of the friend corresponding to the conversation displayed on the position $i$ after receiving all $n$ messages.


-----Examples-----
Input
7 2
1 2 3 2 1 3 2

Output
2
2 1 

Input
10 4
2 3 3 1 1 2 1 2 3 3

Output
3
1 3 2 



-----Note-----

In the first example the list of conversations will change in the following way (in order from the first to last message):

  $[]$;  $[1]$;  $[2, 1]$;  $[3, 2]$;  $[3, 2]$;  $[1, 3]$;  $[1, 3]$;  $[2, 1]$. 

In the second example the list of conversations will change in the following way:

  $[]$;  $[2]$;  $[3, 2]$;  $[3, 2]$;  $[1, 3, 2]$;  and then the list will not change till the end.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Miranda lives in a city containing N junctions and M bidirectional roads between some pairs of these junctions.Miranda is a programming enthusiast - though in  her spare time she does make time for a bit of creative writing . She takes part in Individual Creative Penning Contest organized by the Annual Cultural Melange (ACM ICPC) . The competition is on Sunday and it is already Saturday . Miranda realizes she needs to buy K items for her competition tomorrow . Each of these K items can be found in exactly one junction in her city.  

Miranda has to starts from her school which is located in junction number 1 and ultimately must reach her home , in junction number N . On her way , Miranda must visit each of the K junctions that keep the materials required for her competition . Miranda can visit these K junctions in any order , and in doing so can cross a particular city multiple times if she needs to .   

You must find the minimum distance that Miranda must cover from her school to home such that she visits each of the K junctions atleast once.  

Input
The first line contains the integers N,M and K.
The next M lines are of the form : u v c which denotes there is a bidirectional road joining u and v which is of length c.
The next line contains K integers-the numbers of the junctions that Miranda has to visit on her path .  

Output
Print a single integer-the answer to the problem stated above.  

Constraints
2 ≤ N ≤ 400
1 ≤ M ≤ N*(N-1)/2  
0 ≤ K ≤ 15 
1 ≤ u,v ≤ N,1 ≤ c ≤ 1000  
None of the K junctions that has the material that Miranda needs is 1 or N.

SAMPLE INPUT
3 3 1
1 3 690
2 3 445
2 1 620
2

SAMPLE OUTPUT
1065

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya has an array $a$ consisting of $n$ integers. He wants to remove duplicate (equal) elements.

Petya wants to leave only the rightmost entry (occurrence) for each element of the array. The relative order of the remaining unique elements should not be changed.

Input Specification:
The first line contains a single integer $n$ ($1 \le n \le 50$) — the number of elements in Petya's array.

The following line contains a sequence $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1\,000$) — the Petya's array.

Output Specification:
In the first line print integer $x$ — the number of elements which will be left in Petya's array after he removed the duplicates.

In the second line print $x$ integers separated with a space — Petya's array after he removed the duplicates. For each unique element only the rightmost entry should be left.

Demo Input:
['6\n1 5 5 1 6 1\n', '5\n2 4 2 4 4\n', '5\n6 6 6 6 6\n']

Demo Output:
['3\n5 6 1 \n', '2\n2 4 \n', '1\n6 \n']

Note:
In the first example you should remove two integers $1$, which are in the positions $1$ and $4$. Also you should remove the integer $5$, which is in the position $2$.

In the second example you should remove integer $2$, which is in the position $1$, and two integers $4$, which are in the positions $2$ and $4$.

In the third example you should remove four integers $6$, which are in the positions $1$, $2$, $3$ and $4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to get Zodiac Sign using input ```day``` and ```month```.

For exapmle: 

```python
get_zodiac_sign(1,5) => 'Taurus'
get_zodiac_sign(10,10) => 'Libra'
```

Correct answers are (preloaded): 
```python
SIGNS = ['Capricorn', 'Aquarius', 'Pisces', 'Aries', 'Taurus', 'Gemini', 'Cancer', 'Leo', 'Virgo', 'Libra', 'Scorpio', 'Sagittarius']
```

P.S. Each argument is correct integer number.

WESTERN ASTROLOGY STAR SIGN DATES

* Aries (March 21-April 19)
* Taurus (April 20-May 20)
* Gemini (May 21-June 20)
* Cancer (June 21-July 22)
* Leo (July 23-August 22)
* Virgo (August 23-September 22)
* Libra (September 23-October 22)
* Scorpio (October 23-November 21)
* Sagittarius (November 22-December 21)
* Capricorn (December 22-January 19)
* Aquarius (January 20 to February 18)
* Pisces (February 19 to March 20)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have N items that you want to put them into a knapsack. Item i has value vi, weight wi and limitation mi.

You want to find a subset of items to put such that:

* The total value of the items is as large as possible.
* The items have combined weight at most W, that is capacity of the knapsack.
* You can select at most mi items for ith item.



Find the maximum total value of items in the knapsack.

Constraints

* 1 ≤ N ≤ 100
* 1 ≤ vi ≤ 1,000
* 1 ≤ wi ≤ 1,000
* 1 ≤ mi ≤ 10,000
* 1 ≤ W ≤ 10,000

Input


N W
v1 w1 m1
v2 w2 m2
:
vN wN mN


The first line consists of the integers N and W. In the following N lines, the value, weight and limitation of the i-th item are given.

Output

Print the maximum total values of the items in a line.

Examples

Input

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


Output

12


Input

2 100
1 1 100
2 1 50


Output

150

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## Task
In this kata you'll be given a string of English digits "collapsed" together, like this:

`zeronineoneoneeighttwoseventhreesixfourtwofive`

Your task is to split the string back to digits:

`zero nine one one eight two seven three six four two five`

## Examples
```
three -> three
eightsix -> eight six
fivefourseven -> five four seven
ninethreesixthree -> nine three six three
fivethreefivesixthreenineonesevenoneeight -> five three five six three nine one seven one eight
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* incoming messages for Vasya. The *i*-th message is going to be received after *t**i* minutes. Each message has a cost, which equals to *A* initially. After being received, the cost of a message decreases by *B* each minute (it can become negative). Vasya can read any message after receiving it at any moment of time. After reading the message, Vasya's bank account receives the current cost of this message. Initially, Vasya's bank account is at 0.

Also, each minute Vasya's bank account receives *C*·*k*, where *k* is the amount of received but unread messages.

Vasya's messages are very important to him, and because of that he wants to have all messages read after *T* minutes.

Determine the maximum amount of money Vasya's bank account can hold after *T* minutes.

Input Specification:
The first line contains five integers *n*, *A*, *B*, *C* and *T* (1<=≤<=*n*,<=*A*,<=*B*,<=*C*,<=*T*<=≤<=1000).

The second string contains *n* integers *t**i* (1<=≤<=*t**i*<=≤<=*T*).

Output Specification:
Output one integer  — the answer to the problem.

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

Demo Output:
['20\n', '15\n', '35\n']

Note:
In the first sample the messages must be read immediately after receiving, Vasya receives *A* points for each message, *n*·*A* = 20 in total.

In the second sample the messages can be read at any integer moment.

In the third sample messages must be read at the moment T. This way Vasya has 1, 2, 3, 4 and 0 unread messages at the corresponding minutes, he gets 40 points for them. When reading messages, he receives (5 - 4·3) + (5 - 3·3) + (5 - 2·3) + (5 - 1·3) + 5 =  - 5 points. This is 35 in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Every evening Vitalya sets n alarm clocks to wake up tomorrow. Every alarm clock rings during exactly one minute and is characterized by one integer a_{i} — number of minute after midnight in which it rings. Every alarm clock begins ringing at the beginning of the minute and rings during whole minute. 

Vitalya will definitely wake up if during some m consecutive minutes at least k alarm clocks will begin ringing. Pay attention that Vitalya considers only alarm clocks which begin ringing during given period of time. He doesn't consider alarm clocks which started ringing before given period of time and continues ringing during given period of time.

Vitalya is so tired that he wants to sleep all day long and not to wake up. Find out minimal number of alarm clocks Vitalya should turn off to sleep all next day. Now all alarm clocks are turned on. 


-----Input-----

First line contains three integers n, m and k (1 ≤ k ≤ n ≤ 2·10^5, 1 ≤ m ≤ 10^6) — number of alarm clocks, and conditions of Vitalya's waking up. 

Second line contains sequence of distinct integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6) in which a_{i} equals minute on which i-th alarm clock will ring. Numbers are given in arbitrary order. Vitalya lives in a Berland in which day lasts for 10^6 minutes. 


-----Output-----

Output minimal number of alarm clocks that Vitalya should turn off to sleep all next day long.


-----Examples-----
Input
3 3 2
3 5 1

Output
1

Input
5 10 3
12 8 18 25 1

Output
0

Input
7 7 2
7 3 4 1 6 5 2

Output
6

Input
2 2 2
1 3

Output
0



-----Note-----

In first example Vitalya should turn off first alarm clock which rings at minute 3.

In second example Vitalya shouldn't turn off any alarm clock because there are no interval of 10 consequence minutes in which 3 alarm clocks will ring.

In third example Vitalya should turn off any 6 alarm clocks.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef is hosting a party at his house and N people are invited to it. Everyone has arrived and they are eager to make a group and chit-chat.

The i^{th} person prefers to be in a group of exactly P_{i} people (including himself). A person who is not in a group of preferred size gets upset. Find whether Chef would be able to assign every person to a group such that everyone remains happy.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of people at the party.
- The next line contains the array P — where P_{i} denotes the preferred group size for i^{th} person.

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

For each test case, output YES, if Chef can assign every person to a group such that everyone remains happy. Otherwise output NO.

The output is case-insensitive, meaning that outputs such as yES, YeS, YES and yes mean the same.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$2 ≤ P_{i} ≤ N$
- Sum of $N$ over all test cases does not exceed $10^{5}$.

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

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

----- explanation 1 ------ 
Test case $1$:
- Person $1$ and $3$ can make a group (As both want to be in a group of $2$).
- Person $2$, $4$ and $5$ can make a group (As they all want to be in a group of $3$).

So, there is a possible arrangement that Chef can make so that all of them are happy.

Test case $2$:
- All of the $5$ people can make a group (As all want to be in a group of $5$).

So, there is a possible arrangement that Chef can make so that all of them are happy.

Test case $3$: It can be shown that there is no possible arrangement that Chef can make so that all of them are happy.

Test case $4$: It can be shown that there is no possible arrangement that Chef can make so that all of them are happy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are two strings s and t consisting of lowercase English letters. Determine if the number of non-negative integers i satisfying the following condition is finite, and find the maximum value of such i if the number is finite.
 - There exists a non-negative integer j such that the concatenation of i copies of t is a substring of the concatenation of j copies of s.

-----Notes-----
 - A string a is a substring of another string b if and only if there exists an integer x (0 \leq x \leq |b| - |a|) such that, for any y (1 \leq y \leq |a|), a_y = b_{x+y} holds.
 - We assume that the concatenation of zero copies of any string is the empty string. From the definition above, the empty string is a substring of any string. Thus, for any two strings s and t, i = 0 satisfies the condition in the problem statement.

-----Constraints-----
 - 1 \leq |s| \leq 5 \times 10^5
 - 1 \leq |t| \leq 5 \times 10^5
 - s and t consist of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
s
t

-----Output-----
If the number of non-negative integers i satisfying the following condition is finite, print the maximum value of such i; if the number is infinite, print -1.

-----Sample Input-----
abcabab
ab

-----Sample Output-----
3

The concatenation of three copies of t, ababab, is a substring of the concatenation of two copies of s, abcabababcabab, so i = 3 satisfies the condition.
On the other hand, the concatenation of four copies of t, abababab, is not a substring of the concatenation of any number of copies of s, so i = 4 does not satisfy the condition.
Similarly, any integer greater than 4 does not satisfy the condition, either. Thus, the number of non-negative integers i satisfying the condition is finite, and the maximum value of such i is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An array b is called to be a subarray of a if it forms a continuous subsequence of a, that is, if it is equal to a_l, a_{l + 1}, …, a_r for some l, r.

Suppose m is some known constant. For any array, having m or more elements, let's define it's beauty as the sum of m largest elements of that array. For example: 

  * For array x = [4, 3, 1, 5, 2] and m = 3, the 3 largest elements of x are 5, 4 and 3, so the beauty of x is 5 + 4 + 3 = 12.
  * For array x = [10, 10, 10] and m = 2, the beauty of x is 10 + 10 = 20.



You are given an array a_1, a_2, …, a_n, the value of the said constant m and an integer k. Your need to split the array a into exactly k subarrays such that:

  * Each element from a belongs to exactly one subarray.
  * Each subarray has at least m elements.
  * The sum of all beauties of k subarrays is maximum possible.

Input

The first line contains three integers n, m and k (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ m, 2 ≤ k, m ⋅ k ≤ n) — the number of elements in a, the constant m in the definition of beauty and the number of subarrays to split to.

The second line contains n integers a_1, a_2, …, a_n (-10^9 ≤ a_i ≤ 10^9).

Output

In the first line, print the maximum possible sum of the beauties of the subarrays in the optimal partition.

In the second line, print k-1 integers p_1, p_2, …, p_{k-1} (1 ≤ p_1 < p_2 < … < p_{k-1} < n) representing the partition of the array, in which:

  * All elements with indices from 1 to p_1 belong to the first subarray.
  * All elements with indices from p_1 + 1 to p_2 belong to the second subarray.
  * ….
  * All elements with indices from p_{k-1} + 1 to n belong to the last, k-th subarray.



If there are several optimal partitions, print any of them.

Examples

Input


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


Output


21
3 5 

Input


6 1 4
4 1 3 2 2 3


Output


12
1 3 5 

Input


2 1 2
-1000000000 1000000000


Output


0
1 

Note

In the first example, one of the optimal partitions is [5, 2, 5], [2, 4], [1, 1, 3, 2].

  * The beauty of the subarray [5, 2, 5] is 5 + 5 = 10. 
  * The beauty of the subarray [2, 4] is 2 + 4 = 6. 
  * The beauty of the subarray [1, 1, 3, 2] is 3 + 2 = 5. 



The sum of their beauties is 10 + 6 + 5 = 21.

In the second example, one optimal partition is [4], [1, 3], [2, 2], [3].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A prime number is an integer greater than $1$ that has no positive divisors other than $1$ and itself.

We call a number megaprime if it is prime and all of its individual digits are prime. For example, $53$ is megaprime because it is prime and all its digits ($5$ and $3$) are prime; however, $35$ is not megaprime because it is not prime (it's divisible by $5$ and $7$), and $13$ is not megaprime because it has a non-prime digit ($1$ is not prime).

Given two long integers, $first$ and $last$, find and print the total number of megaprime numbers in the inclusive range between $first$ and $last$.

Input Format

Two space-separated long integers describing the respective values of $first$ and $last$.

Constraints

$1\leq first\leq last\leq10^{15}$
$last-first\leq10^9$

Output Format

Print a long integer denoting the total number of megaprimes in the inclusive interval between $first$ and $last$.

Sample Input 0
1 100

Sample Output 0
8

Explanation 0

There are eight megaprime numbers in the inclusive range from $first=1$ to $last=100$ (i.e., $2$, $3$, $5$, $7$, $23$, $37$, $53$, and $73$), so we print $8$ as our answer.

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