vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Little Dima and Equation

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Little Dima misbehaved during a math lesson a lot and the nasty teacher Mr. Pickles gave him the following problem as a punishment. 

Find all integer solutions *x* (0<=&lt;<=*x*<=&lt;<=109) of the equation:

where *a*, *b*, *c* are some predetermined constant values and function *s*(*x*) determines the sum of all digits in the decimal representation of number *x*.

The teacher gives this problem to Dima for each lesson. He changes only the parameters of the equation: *a*, *b*, *c*. Dima got sick of getting bad marks and he asks you to help him solve this challenging problem.

Input Specification:
The first line contains three space-separated integers: *a*,<=*b*,<=*c* (1<=≤<=*a*<=≤<=5; 1<=≤<=*b*<=≤<=10000; <=-<=10000<=≤<=*c*<=≤<=10000).

Output Specification:
Print integer *n* — the number of the solutions that you've found. Next print *n* integers in the increasing order — the solutions of the given equation. Print only integer solutions that are larger than zero and strictly less than 109.

Demo Input:
['3 2 8\n', '1 2 -18\n', '2 2 -1\n']

Demo Output:
['3\n10 2008 13726 ', '0\n', '4\n1 31 337 967 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Some number of chocolate pieces were prepared for a training camp.
The camp had N participants and lasted for D days.
The i-th participant (1 \leq i \leq N) ate one chocolate piece on each of the following days in the camp: the 1-st day, the (A_i + 1)-th day, the (2A_i + 1)-th day, and so on.
As a result, there were X chocolate pieces remaining at the end of the camp. During the camp, nobody except the participants ate chocolate pieces.
Find the number of chocolate pieces prepared at the beginning of the camp.

-----Constraints-----
 - 1 \leq N \leq 100
 - 1 \leq D \leq 100
 - 1 \leq X \leq 100
 - 1 \leq A_i \leq 100 (1 \leq i \leq N)
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
D X
A_1
A_2
:
A_N

-----Output-----
Find the number of chocolate pieces prepared at the beginning of the camp.

-----Sample Input-----
3
7 1
2
5
10

-----Sample Output-----
8

The camp has 3 participants and lasts for 7 days.
Each participant eats chocolate pieces as follows:
 - The first participant eats one chocolate piece on Day 1, 3, 5 and 7, for a total of four.
 - The second participant eats one chocolate piece on Day 1 and 6, for a total of two.
 - The third participant eats one chocolate piece only on Day 1, for a total of one.
Since the number of pieces remaining at the end of the camp is one, the number of pieces prepared at the beginning of the camp is 1 + 4 + 2 + 1 = 8.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
On the way to school, Karen became fixated on the puzzle game on her phone!

The game is played as follows. In each level, you have a grid with *n* rows and *m* columns. Each cell originally contains the number 0.

One move consists of choosing one row or column, and adding 1 to all of the cells in that row or column.

To win the level, after all the moves, the number in the cell at the *i*-th row and *j*-th column should be equal to *g**i*,<=*j*.

Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this task!

Input Specification:
The first line of input contains two integers, *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100), the number of rows and the number of columns in the grid, respectively.

The next *n* lines each contain *m* integers. In particular, the *j*-th integer in the *i*-th of these rows contains *g**i*,<=*j* (0<=≤<=*g**i*,<=*j*<=≤<=500).

Output Specification:
If there is an error and it is actually not possible to beat the level, output a single integer -1.

Otherwise, on the first line, output a single integer *k*, the minimum number of moves necessary to beat the level.

The next *k* lines should each contain one of the following, describing the moves in the order they must be done:
 -  row *x*, (1<=≤<=*x*<=≤<=*n*) describing a move of the form "choose the *x*-th row". -  col *x*, (1<=≤<=*x*<=≤<=*m*) describing a move of the form "choose the *x*-th column". 
If there are multiple optimal solutions, output any one of them.

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

Demo Output:
['4\nrow 1\nrow 1\ncol 4\nrow 3\n', '-1\n', '3\nrow 1\nrow 2\nrow 3\n']

Note:
In the first test case, Karen has a grid with 3 rows and 5 columns. She can perform the following 4 moves to beat the level:

In the second test case, Karen has a grid with 3 rows and 3 columns. It is clear that it is impossible to beat the level; performing any move will create three 1s on the grid, but it is required to only have one 1 in the center.

In the third test case, Karen has a grid with 3 rows and 3 columns. She can perform the following 3 moves to beat the level:

Note that this is not the only solution; another solution, among others, is col 1, col 2, col 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, we are going to see how a Hash (or Map or dict) can be used to keep track of characters in a string. 

Consider two strings `"aabcdefg"` and `"fbd"`. How many characters do we have to remove from the first string to get the second string?  Although not the only way to solve this, we could create a Hash of counts for each string and see which character counts are different. That should get us close to the answer. I will leave the rest to you. 

For this example, `solve("aabcdefg","fbd") = 5`. Also, `solve("xyz","yxxz") = 0`, because we cannot get second string from the first since the second string is longer.

More examples in the test cases.

Good luck!

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Palindromic characteristics of string *s* with length |*s*| is a sequence of |*s*| integers, where *k*-th number is the total number of non-empty substrings of *s* which are *k*-palindromes.

A string is 1-palindrome if and only if it reads the same backward as forward.

A string is *k*-palindrome (*k*<=&gt;<=1) if and only if: 
 1.  Its left half equals to its right half. 1.  Its left and right halfs are non-empty (*k*<=-<=1)-palindromes. 
The left half of string *t* is its prefix of length ⌊|*t*|<=/<=2⌋, and right half — the suffix of the same length. ⌊|*t*|<=/<=2⌋ denotes the length of string *t* divided by 2, rounded down.

Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times.

Input Specification:
The first line contains the string *s* (1<=≤<=|*s*|<=≤<=5000) consisting of lowercase English letters.

Output Specification:
Print |*s*| integers — palindromic characteristics of string *s*.

Demo Input:
['abba\n', 'abacaba\n']

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

Note:
In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A subarray A[i], A[i+1], ..., A[j] of A is said to be turbulent if and only if:

For i <= k < j, A[k] > A[k+1] when k is odd, and A[k] < A[k+1] when k is even;
OR, for i <= k < j, A[k] > A[k+1] when k is even, and A[k] < A[k+1] when k is odd.

That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray.
Return the length of a maximum size turbulent subarray of A.
 

Example 1:
Input: [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: (A[1] > A[2] < A[3] > A[4] < A[5])


Example 2:
Input: [4,8,12,16]
Output: 2


Example 3:
Input: [100]
Output: 1




 
Note:

1 <= A.length <= 40000
0 <= A[i] <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mole decided to live in an abandoned mine. The structure of the mine is represented by a simple connected undirected graph which consists of N vertices numbered 1 through N and M edges. The i-th edge connects Vertices a_i and b_i, and it costs c_i yen (the currency of Japan) to remove it.

Mole would like to remove some of the edges so that there is exactly one path from Vertex 1 to Vertex N that does not visit the same vertex more than once. Find the minimum budget needed to achieve this.

Constraints

* 2 \leq N \leq 15
* N-1 \leq M \leq N(N-1)/2
* 1 \leq a_i, b_i \leq N
* 1 \leq c_i \leq 10^{6}
* There are neither multiple edges nor self-loops in the given graph.
* The given graph is connected.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1 c_1
:
a_M b_M c_M


Output

Print the answer.

Examples

Input

4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100


Output

200


Input

2 1
1 2 1


Output

0


Input

15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491


Output

133677

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The math faculty of Berland State University has suffered the sudden drop in the math skills of enrolling students. This year the highest grade on the entrance math test was 8. Out of 100! Thus, the decision was made to make the test easier.

Future students will be asked just a single question. They are given a sequence of integer numbers $a_1, a_2, \dots, a_n$, each number is from $1$ to $3$ and $a_i \ne a_{i + 1}$ for each valid $i$. The $i$-th number represents a type of the $i$-th figure:

  circle;  isosceles triangle with the length of height equal to the length of base;  square. 

The figures of the given sequence are placed somewhere on a Cartesian plane in such a way that:

  $(i + 1)$-th figure is inscribed into the $i$-th one;  each triangle base is parallel to OX;  the triangle is oriented in such a way that the vertex opposite to its base is at the top;  each square sides are parallel to the axes;  for each $i$ from $2$ to $n$ figure $i$ has the maximum possible length of side for triangle and square and maximum radius for circle. 

Note that the construction is unique for some fixed position and size of just the first figure.

The task is to calculate the number of distinct points (not necessarily with integer coordinates) where figures touch. The trick is, however, that the number is sometimes infinite. But that won't make the task difficult for you, will it?

So can you pass the math test and enroll into Berland State University?


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 100$) — the number of figures.

The second line contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3$, $a_i \ne a_{i + 1}$) — types of the figures.


-----Output-----

The first line should contain either the word "Infinite" if the number of distinct points where figures touch is infinite or "Finite" otherwise.

If the number is finite than print it in the second line. It's guaranteed that the number fits into 32-bit integer type.


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

Output
Finite
7

Input
3
1 2 3

Output
Infinite



-----Note-----

Here are the glorious pictures for the examples. Note that the triangle is not equilateral but just isosceles with the length of height equal to the length of base. Thus it fits into a square in a unique way.

The distinct points where figures touch are marked red.

In the second example the triangle and the square touch each other for the whole segment, it contains infinite number of points.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Salmon has some hidden numbers that he wants you to find!

Given an integer $N$, find and output any two integers A and B such that:
* $1 ≤ A, B ≤ 10^{9}$, and
* $A*B = N$.

------ Input: ------
The first line of input consists of a single integer $T$ ($1 ≤ T ≤ 10^{5}$) -- the number of testcases.

The next $T$ lines will consist of one integer, $N$ ($1 ≤ N ≤ 10^{9}$).

------ Output: ------
For each of the $T$ testcases, output two space-separated integers $A$ and $B$.

------ Subtasks ------
* Subtask 1 [100 points]: No additional constraints.

----- Sample Input 1 ------ 
5
1
3
5
8
10
----- Sample Output 1 ------ 
1 1
1 3
1 5
1 8
2 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to solve some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

-----Sample Input:-----
4
1
2
3
4

-----Sample Output:-----
*
*
*
*
***
***
*
*
***
***
*****
*****
*
*
***
***
*****
*****
*******
*******

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a String S, reverse the string without reversing its individual words. Words are separated by dots.
Example 1:
Input:
S = i.like.this.program.very.much
Output: much.very.program.this.like.i
Explanation: After reversing the whole
string(not individual words), the input
string becomes
much.very.program.this.like.i
Example 2:
Input:
S = pqr.mno
Output: mno.pqr
Explanation: After reversing the whole
string , the input string becomes
mno.pqr
Your Task:
You dont need to read input or print anything. Complete the function reverseWords() which takes string S as input parameter and returns a string containing the words in reversed order. Each word in the returning string should also be separated by '.' 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1 <= |S| <= 10^{5}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A renowned abstract artist Sasha, drawing inspiration from nowhere, decided to paint a picture entitled "Special Olympics". He justly thought that, if the regular Olympic games have five rings, then the Special ones will do with exactly two rings just fine.

Let us remind you that a ring is a region located between two concentric circles with radii *r* and *R* (*r*<=&lt;<=*R*). These radii are called internal and external, respectively. Concentric circles are circles with centers located at the same point.

Soon a white canvas, which can be considered as an infinite Cartesian plane, had two perfect rings, painted with solid black paint. As Sasha is very impulsive, the rings could have different radii and sizes, they intersect and overlap with each other in any way. We know only one thing for sure: the centers of the pair of rings are not the same.

When Sasha got tired and fell into a deep sleep, a girl called Ilona came into the room and wanted to cut a circle for the sake of good memories. To make the circle beautiful, she decided to cut along the contour.

We'll consider a contour to be a continuous closed line through which there is transition from one color to another (see notes for clarification). If the contour takes the form of a circle, then the result will be cutting out a circle, which Iona wants.

But the girl's inquisitive mathematical mind does not rest: how many ways are there to cut a circle out of the canvas?

Input Specification:
The input contains two lines. 

Each line has four space-separated integers *x**i*, *y**i*, *r**i*, *R**i*, that describe the *i*-th ring; *x**i* and *y**i* are coordinates of the ring's center, *r**i* and *R**i* are the internal and external radii of the ring correspondingly (<=-<=100<=≤<=*x**i*,<=*y**i*<=≤<=100; 1<=≤<=*r**i*<=&lt;<=*R**i*<=≤<=100). 

It is guaranteed that the centers of the rings do not coinside.

Output Specification:
A single integer — the number of ways to cut out a circle from the canvas.

Demo Input:
['60 60 45 55\n80 80 8 32\n', '60 60 45 55\n80 60 15 25\n', '50 50 35 45\n90 50 35 45\n']

Demo Output:
['1', '4', '0']

Note:
Figures for test samples are given below. The possible cuts are marked with red dotted line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An exam for n students will take place in a long and narrow room, so the students will sit in a line in some order. The teacher suspects that students with adjacent numbers (i and i + 1) always studied side by side and became friends and if they take an exam sitting next to each other, they will help each other for sure.

Your task is to choose the maximum number of students and make such an arrangement of students in the room that no two students with adjacent numbers sit side by side.


-----Input-----

A single line contains integer n (1 ≤ n ≤ 5000) — the number of students at an exam.


-----Output-----

In the first line print integer k — the maximum number of students who can be seated so that no two students with adjacent numbers sit next to each other.

In the second line print k distinct integers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ n), where a_{i} is the number of the student on the i-th position. The students on adjacent positions mustn't have adjacent numbers. Formally, the following should be true: |a_{i} - a_{i} + 1| ≠ 1 for all i from 1 to k - 1.

If there are several possible answers, output any of them.


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

Output
2
1 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A tree is a connected graph without cycles.

Two trees, consisting of n vertices each, are called isomorphic if there exists a permutation p: {1, ..., n} → {1, ..., n} such that the edge (u, v) is present in the first tree if and only if the edge (pu, pv) is present in the second tree.

Vertex of the tree is called internal if its degree is greater than or equal to two.

Count the number of different non-isomorphic trees, consisting of n vertices, such that the degree of each internal vertex is exactly d. Print the answer over the given prime modulo mod.

Input

The single line of the input contains three integers n, d and mod (1 ≤ n ≤ 1000, 2 ≤ d ≤ 10, 108 ≤ mod ≤ 109) — the number of vertices in the tree, the degree of internal vertices and the prime modulo.

Output

Print the number of trees over the modulo mod.

Examples

Input

5 2 433416647


Output

1


Input

10 3 409693891


Output

2


Input

65 4 177545087


Output

910726

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Golu wants to find out the sum of Lucky numbers.Lucky numbers are those numbers which contain exactly two set bits.This task is very diffcult for him.So Help Golu to find sum of those numbers which exactly contain two set bits upto a given number N.

3 5 10 are lucky numbers where 7 14 are not.

INPUT First line contain number of test cases T.Each test case contains a single number N.
OUTPUT Print sum of all Lucky Numbers upto N.Output may be large so take modulo with 1000000007.  
Constraints 

1 ≤ T ≤ 10^5
1 ≤ N ≤ 10^18

NOTE: Since value of test cases and n is really large, please use fast I/O optimization techniques. 

SAMPLE INPUT
1
5

SAMPLE OUTPUT
8

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

Time Limit: 3 seconds

Memory Limit: 256 megabytes

Problem Description:
The Berland capital (as you very well know) contains *n* junctions, some pairs of which are connected by two-way roads. Unfortunately, the number of traffic jams in the capital has increased dramatically, that's why it was decided to build several new roads. Every road should connect two junctions. 

The city administration noticed that in the cities of all the developed countries between any two roads one can drive along at least two paths so that the paths don't share any roads (but they may share the same junction). The administration decided to add the minimal number of roads so that this rules was fulfilled in the Berland capital as well. In the city road network should exist no more than one road between every pair of junctions before or after the reform.

Input Specification:
The first input line contains a pair of integers *n*, *m* (2<=≤<=*n*<=≤<=900,<=1<=≤<=*m*<=≤<=100000), where *n* is the number of junctions and *m* is the number of roads. Each of the following *m* lines contains a description of a road that is given by the numbers of the connected junctions *a**i*,<=*b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*). The junctions are numbered from 1 to *n*. It is possible to reach any junction of the city from any other one moving along roads.

Output Specification:
On the first line print *t* — the number of added roads. Then on *t* lines print the descriptions of the added roads in the format of the input data. You can use any order of printing the roads themselves as well as the junctions linked by every road. If there are several solutions to that problem, print any of them.

If the capital doesn't need the reform, print the single number 0.

If there's no solution, print the single number -1.

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

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

Note:
none

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