13道题，全是英文题，懒得没拿词典，后来才知道可以用电子词典(当然正经比赛里面是不可以的。先写一下我做出来的题解在总结吧。

MaratonIME helps Pablito

Description:
♬ Caloventor tiene miedo… ♬
Benedetto, Nathan
As is well known by any cultured person, rats are the smartest beings on earth. Followed directly by dolphins.

MaratonIME knows about the species hierarchy and uses this knowledge in it’s regard. Usually, when they need some resource, they know it’s always useful to have a smart rat available. Unfortunately, rats are not very fond of us, primates, and will only help us if they owe us some favour.

With that in mind, MaratonIME decided to help a little rat called Pablito. Pablito is studying rat’s genealogy, to help with cloning and genetic mapping. luckily, the way rats identify themselves make the job much easier.

The rat society is, historically, matriarchal. At first, there were little families, each of which had it’s own leading matriarch. At that time, it was decided that rats would organize themselves according to the following rules:

Each martiarch had an id number greater than one.
Each of these ids were chosen in a way such that they would have the least amount of divisors possible.
Each family member had the same id as the matriarch.
The id of any newborn rat would be the product of its parents id’s.
For instance, the offspring of a rat with id 6 and another with id 7 is 42.

Pablito needs to know if two given rats have a common ancestor, but his only tool is the id number of each of the two rats, which is always a positive integer greater than 1 with no more than 16 digits. Can you help him?

Create a program that decides if a pair of rats have some common ancestor.

Input

The input begins with a positive integer t ≤ 105, the number of test cases.
After that, follows t lines, each with two integers ai e bi identifying two rats.
Every rat’s id is a positive integer greater than 1 and with no more than 16 digits.

Output

For each test case, print “Sim” if the rats ai and bi share a common ancestor and “Nao” otherwise.

Example
Input

2
2 4
3 5

Output

Sim
Nao

Problem solving:

Code:

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
long long n,a,b;
cin>>n;
while(n--)
{
cin>>a>>b;
if(__gcd(a,b)==1)    puts("Nao");
else    puts("Sim");
}
}


MaratonIME plays Cîrokime

Description:
Have you ever seen flavored vodka?
Everaldo, Glauber
The MaratonIME members like to have fun. As they enjoy having fun so much, they have invented a game named “Cîrokime”. The game works as follows:

First, n cups with Cîroc1 are lined up. In front of the i-th cup a number ai is written. It is guaranteed that ai < ai + 1, for all 1 ≤ i < n. Then, the numbers are covered and the game starts.

The player must then find the cup that has a certain number x. It is guaranteed that this cup exists. For this, he has to choose a cup i and drink the beverage. Then, the cup’s number ai is revealed and if this number is equal to x the game finished. Otherwise, the player has to choose another cup and so on.

“Cîrokime” is a traditional game among MaratonIME members, they play it every party. At the last party, Sussu had to drink all of the n cups because he found the right cup only at the end. He got sick for drinking so much and had to be carried home3

However, the DESMAME4 is scheduled for May 13 and Sussu wants to restore his dignity. For this, he wants to know, in the worst case, what is the maximum number of cups that he will have to drink if he plays in the optimal way.

Input

The first line has a single integer n, the number of cups. The second line has n integers ai, the values hidden in each cup.
1 ≤ n ≤ 1e5
For all i, 1 ≤ ai ≤ 1e9
For i < n, ai < ai + 1

Output

The output has a single line with a single integer: the minimum number of cups that Sussu should drink, in the worst case, if he plays in the optimal way.

Examples
Input

3
2 5 7

Output

2

Input

8
1 2 3 4 5 6 7 8

Output

4

Note

1: Cîroc is a vodka brand made in France, known by its high sales price in market2
2: Balalaika also works
3: Based on real facts
4: Pre-BIFE5 party
5: University games that IME6 attends
6: Institute of Mathematics and Statistics

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,a;
scanf("%lld",&n);
for(int i=0;i<n;i++)    scanf("%lld",&a);
ll ans=0;
while(n)
{
n/=2;
ans++;
}
printf("%lld\n",ans);
}


MaratonIME plays Nim

Description:
Ai Fox!
UnionFind, Germano
You open your eyes, but everything remains dark. The world is dark, and everything shakes. You realize you are locked in, but before desperation takes hold, you hear the door opening and the light invades your sight and blinds you for a few moments.

They help you out, you had been locked inside a trunk. You don’t know the masked faces before you, but remember that in the last competitive programming practice they told you that “the beginning is yet to come”. “So this is the fabled MaratonIME’s initiation challenge”, you had heard rumors of this event, and you feel honored to be chosen.

After walking into and abandoned building, they sit you on an old chair. The first test is to watch a soccer game without any show of excitement. Easy. The second is to install Linux on a notebook in less than 5 minutes. You were prepared, carrying the Arch Linux pendrive as usual, just in case. You face more tests, and manage to pass all of them despite a few difficulties.

Hours go by, the members remove their masks, and each take a coin out of their pocket. “I won! And I even got rich” you think, but realize they place the coins in a table in front of you, divided in two piles. Renzo, MaratonIME’s great boss, takes a chair and sits in front of you. You will play a match of Nim, and if you win you will become an honorary member of MaratonIME, that is, you win a balloon.

Nim is a game of two players, alternating their turns. Two piles of coins are placed on a table and in each turn you can remove any non zero quantity of coins from one of the piles. The last player to take their turn (leaving both piles empty) wins.

You start the game. So it would not be unfair, it is guaranteed that it is possible for you to win. Write a program than beats Renzo 100% of the time.

Input

In the first line, two integers, x and y, the size of the piles, such that 0 ≤ x, y ≤ 1e4. It is guaranteed that you can win the game.

Interaction

In your turn, print two integers, i and x, where i is the number of the pile from which you will remove the coins (), and x is the number of coins you will remove (x ≥ 1, such that i has at least x coins).
In Renzo’s turn, read two integers, in the same format as in your turn.

Example
Input

2 1
1 1

Output

1 1
2 1

Note

Of course we do not do an initiation challenge like this :P
In the example, we have a pile with 2 coins and another with 1. You remove 1 coin from the first pile, and now no matter what coin Renzo removes, you can remove the other and win.
Remember, after printing your play, flush the output, like: fflush(stdout); in C, cout.flush(); in C++, or sys.stdout.flush() in Python.

Problem solving:

Code:

/**
*　　　　　　　　┏┓　　 　┏┓
* 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓
* 　　　　　　　┃　　　　　　　┃
* 　　　　　　　┃　　　━　　 　┃
* 　　　　　　　┃　＞　　　＜　┃
* 　　　　　　　┃　　　　　　　┃
* 　　　　　　　┃...　⌒　... 　┃
* 　　　　　　　┃　　　　　　　┃
* 　　　　　　　┗━┓　　　┏━┛
* 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting
* 　　　　　　　　　┃　　　┃   神兽保佑,代码无bug
* 　　　　　　　　　┃　　　┃
* 　　　　　　　　　┃　　　┃
* 　　　　　　　　　┃　　　┃
* 　　　　　　　　　┃　　　┃
* 　　　　　　　　　┃　　　┗━━━┓
* 　　　　　　　　　┃　　　　　　　┣┓
* 　　　　　　　　　┃　　　　　　　┏┛
* 　　　　　　　　　┗┓┓┏━┳┓┏┛
* 　　　　　　　　　　┃┫┫　┃┫┫
* 　　　　　　　　　　┗┻┛　┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
//                            _ooOoo_
//                           o8888888o
//                           88" . "88
//                           (| -_- |)
//                           O\  =  /O
//                        ____/---'\____
//                      .'  \|     |//  .
//                     /  \|||  :  |||//  \
//                    /  _||||| -:- |||||-  \
//                    |   | \\  -  /// |   |
//                    | \_|  ''\---/''  |   |
//                    \  .-\__  -  ___/-. /
//                  ___. .'  /--.--\  . . __
//               ."" '<  .___\_<|>_/___.'  >'"".
//              | | :  - \.;\ _ /;./ -  : | |
//              \  \ -.   \_ __\ /__ _/   .- /  /
//         ======-.____-.___\_____/___.-____.-'======
//                            =---='
//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//


MaratonIME plays Chess

Description:
This problem is boring as duck.
Kawakami, Marcos
Our dear Nathan, when a little child, used to like chess a lot, but this was a long time ago. One of these days he was challenged by @luisgust to a chess match and, as he is a guy that likes hard challenges, he accepted it. The problem is that Nathan keeps forgetting the rules of the game, so he asked you to help him determine if a given opponent’s piece can be captured in one move.

Chess, in MaratonIME, is represented as a matrix of characters. Instead of playing with black and white pieces, they play with uppercase and lowercase letters. Nathan has chosen to play with the lowercase letters.

Besides that, as usual, the positions on the matrix are given in the following coordinates system: Each position is a pair with a character between a and h (inclusive), representing the column, and an integer between 1 and 8 (inclusive), representing the row. For exemple, the position d2 refers to the fourth column (from left to right) and second row (from bottom to top), and the position f6 refers to the sixth column and sixth row. Lowercase letters start on the bottom of the grid, on lines 1 and 2.

Here position A is adjacent position B if A shares a vertex with B, that is, if the distance between their rows is at most one and the distance between their columns is at most one. For example, the position c4 is adjacent to 8 positions: b3, b4, b5, c3, c5, d3, d4 and d5.

They decided to play a simplified version of chess. To help you, they gave you the following manual on how to play it:

The pawn, represented by p or P, can capture pieces that share a diagonal and is in front of it, that is, the lowercase pawn on c4 can capture pieces at b5 or d5.
The knight, represented by c or C, makes L-shaped moves in any of the 8 possible directions, that is, it moves two positions in any direction and after that one position in a direction that is perpenticular to the first one. A knight on c4 can capture, in one move, pieces on positions a3, a5, b2, b6, d2, d6, e3 and e5.
The rook, represented by t or T, can capture pieces that are on the same row or the same column as it, as long as no other piece lies between them. For example, a rook on c4 can capture any piece on column c or row 4, as long as there is no other piece in between. If the rook is on c4 and there is another piece on c6, the rook can’t capture pieces on c7 and c8.
The bishop, represented by b or B, can capture any piece on one of its diagonals as long as there are no piece between them (diagonaly). For example, the bishop on c4 can capture a piece on f7 as long as there are no piece on d5 and e6.
The queen, represented by r or R, can capture any piece that lies on the same row, column or diagonal, given there are no pieces in between, as if it were a bishop and a rook at the same time.
The king, represented by k or K, can capture any piece that is adjacent to it.
The character . represents an empty position.
Given a matrix representing a chess board and an opponent’s piece, your program needs to determine whether you can capture it with one of your pieces. It is guaranteed that each player has at most two bishops, two rooks, two knights, eight pawns, one king and one queen.

Input

The input begins with 8 lines with 8 characters each, representing the chess board. The first line contains the characters on the positions a8, b8, … , h8. The second line contains the characters on positions a7, b7, … , h7, and so on. After that follows a line containing the position of the opponent’s piece you wish to capture.

Output

Print a single line containing the word Sim if it is possible to capture the piece or Nao otherwise.

Examples
Input

TCBRKBCT
PPPPPPPP
……..
……..
……..
……..
pppppppp
tcbrkbct
d8

Output

Nao

Input

……..
……..
……..
..R…..
…p….
……..
……..
……..
c5

Output

Sim

Problem solving:

Code:

/**
*　　　　　　　　┏┓　　 　┏┓
* 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓
* 　　　　　　　┃　　　　　　　┃
* 　　　　　　　┃　　　━　　 　┃
* 　　　　　　　┃　＞　　　＜　┃
* 　　　　　　　┃　　　　　　　┃
* 　　　　　　　┃...　⌒　... 　┃
* 　　　　　　　┃　　　　　　　┃
* 　　　　　　　┗━┓　　　┏━┛
* 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting
* 　　　　　　　　　┃　　　┃   神兽保佑,代码无bug
* 　　　　　　　　　┃　　　┃
* 　　　　　　　　　┃　　　┃
* 　　　　　　　　　┃　　　┃
* 　　　　　　　　　┃　　　┃
* 　　　　　　　　　┃　　　┗━━━┓
* 　　　　　　　　　┃　　　　　　　┣┓
* 　　　　　　　　　┃　　　　　　　┏┛
* 　　　　　　　　　┗┓┓┏━┳┓┏┛
* 　　　　　　　　　　┃┫┫　┃┫┫
* 　　　　　　　　　　┗┻┛　┗┻┛
*/
// warm heart, wagging tail,and a smile just for you!
//
//                            _ooOoo_
//                           o8888888o
//                           88" . "88
//                           (| -_- |)
//                           O\  =  /O
//                        ____/---'\____
//                      .'  \|     |//  .
//                     /  \|||  :  |||//  \
//                    /  _||||| -:- |||||-  \
//                    |   | \\  -  /// |   |
//                    | \_|  ''\---/''  |   |
//                    \  .-\__  -  ___/-. /
//                  ___. .'  /--.--\  . . __
//               ."" '<  .___\_<|>_/___.'  >'"".
//              | | :  - \.;\ _ /;./ -  : | |
//              \  \ -.   \_ __\ /__ _/   .- /  /
//         ======-.____-.___\_____/___.-____.-'======
//                            =---='
//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//


MaratonIME rides the university bus

Description:
If we organize it correctly, …
Unknown
To make the trip to the subway less boring and tiring, the SPSU, Sao Paulo State University, tried one of its most famous inventions: buses with Infinite Inner Length! In such a modern engineering wonder, there’s always a couple of empty seats for the students to sit and chat during the trip.

MaratonIME crew is very popular, so popular that they have friends at every SPSU institute. Like everyone else from this university, they need to take the bus after a long day learning how to fix the Wi-Fi network. Because they don’t practice sports like rowing, every SPSU student sits right after entering the bus, making pairs whenever possible. Thinking about that, Gi, an ICPC expert, comes with a problem to think on the way to the subway: given a number n which indicates the number of institutes at SPSU and n integers ai representing the amount of people waiting for the bus at the institute i, Gi wants to know for m pairs lj, rj (lj ≤ rj) if all the people waiting for the bus at any point between lj e rj (inclusive) took an empty bus, they could sit together in pairs (nobody would sit alone).

Input

The input consist in one line with two integers n and m, the number of institutes and the number of Gi’s questions. In the second line there are n integers ai, the number of people waiting for the bus at the ith institute. Then follows m lines with two integers each, li and ri, the first and last institute of Gi’s question.
1 ≤ n, m ≤ 1e5
0 ≤ ai ≤ 1e5
1 ≤ li ≤ ri ≤ n

Output

Output “Sim” if it is possible to organize all the pairs in a way nobody sits alone or “Nao” otherwise.

Example
Input

5 2
1 4 10 3 2
3 5
2 3

Output

Nao
Sim

Note

In the first sample we have 5 institutes with 1, 4, 10, 3 and 2 students. Gi asks if it is possible to form only couples if the ones between the 3rd and the 5th institutes takes an empty bus and the ones between the 2nd and the 3rd. For the first we have 15 so we can’t and for the second we have 14 so we can.

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[213344],b[213344];
int main()
{
ll n,m,x,y;
cin>>n>>m;
for(int i=0;i<n;i++)    cin>>a[i];
b[0]=a[0];
for(int i=1;i<n;i++)    b[i]=b[i-1]+a[i];
while(m--)
{
cin>>x>>y;
x--,y--;
if((b[y]-b[x-1])%2!=0)    puts("Nao");
else    puts("Sim");
}
}


MaratonIME attends the lecture (or not)

Description:
Has the prof taken attendance yet?
Student, IME’s
In MaratonIME, as many other groups, some students want to attend lectures just enough to not be flunked by frequency (as we know, in USP, University of Sao Paulo, it is necessary to have 70 percent frequency), however some others are dedicated and try to accomplish the most frequency percent possible, going to school even when they are ill or tired. Curiously, there is not any other kind of students in MaratonIME.

Wood, an old MaratonIME’s member, needs help. He is taking the course MAC4815162342, and attended k of m lectures that were given. Consider that MAC4815162342 has n lectures in total per semester. He ask you to help finding the best way to accomplish his objectives, but, as you are new in MaratonIME, you don’t know the kind of student that he is. Embarassed to ask more, you decide to solve two problems, so there is not way to go wrong.

Input

The input consists of a just one line. In this line, you are given three integers n, m and k, with 1 ≤ n ≤ 1e7 and 0 ≤ k ≤ m ≤ n.
n is the number of lectures of MAC4815162342 per semester, m is the quantity of lectures that were given and k is the number of lectures attended by Wood.

Output

In the first line, print the minimum number of lectures that Wood needs to attend to accomplish at least 70% frequency, or  - 1 if it is impossible to accomplish 70% frequency.
In the second line, print the maximum frequency percent that Wood can accomplish, if he goes to all of the lectures from the next lecture. This value has to be rounded down to the closest integer. Don’t print ‘%’.

Examples
Input

10 5 2

Output

5
70

Input

11 2 1

Output

7
90

Note

On the second example, the maximum percentage that Wood can get is 90.9090.

Problem solving:

Code:

a,b,c=input().split()
a=eval(a)
b=eval(b)
c=eval(c)
x=a-b
y=int((a*70+99)/100)   #精度问题
z=y-c
if x<z:
print("-1")
else:
print(max(0,int(y)-c)) #处理如果当前出勤率已经到了%70的情况
ans=int((x+c)*100/a)
print(ans)


MaratonIME goes rowing

Description:
Speed down, Colombooo!!!
rowing coach, Gabi
As common sense tells us, competitive programmers excel at rowing. The olympic lane is a wonderful place to row, run and work out. What few take their time to appreciate are the capybaras that inhabit the region. Capybaras are fascinating animals! Aside from their beauty, they possess many interesting behaviours. Did you know that capybaras can live in packs as big as 100 individuals?

In a pleasant sunny morning, Yan was running, as usual. Watching the capybaras, he noticed that they would line up to sunbath. Each capybara was paired with another one, and only another one. Two capybaras can be paired if and only if both see each other. A capybara sees everything in the direction it is looking.

Curious, Yan decided to represent the capybaras by the letters A and B, where A indicates that the capybara is looking right, and B indicates that the capybara is looking left.

For example, the sequence AABABB accurately represents capybaras sunbathing, because it is possible to pair every capybara according to the rules above. Yan was so fascinate by this that he slipped and felt into the water, messing his representations. He was able to recover some, but now they are all messed up with each other. Can you help him and find out if a given sequence represent capybaras sunbathing?

Input

Every instance contains a sequence S of characters, composed only of ‘A’ and ‘B’ – Yan’s representation. You may assume that 1 ≤ |S| ≤ 105.

Output

The output should contain a single line. Print “Sim” if the sequence represents capybaras sunbathing, or “Nao” otherwise.

Example
Input

AABABB

Output

Sim

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
int x=0,y=0;
cin>>s;
if(s[0]=='B'||s[s.size()-1]=='A')
puts("Nao");
else
{
for(int i=0;i<s.size();i++)
{
if(s[i]=='A')x++;
else y++;
}
if(x!=y)    puts("Nao");
else    puts("Sim");
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int,int> pii;

int main()
{
ios::sync_with_stdio(false);
string s;
cin>>s;
stack<int> st;
for (int i = 0;i < s.size();i ++)
{
if (s[i] == 'A')
st.push(1);
else
{
if (!st.empty()) st.pop();
else
{
cout<<"Nao"<<'\n';
return 0;
}
}
}
if (st.empty()) cout<<"Sim"<<'\n';
else cout<<"Nao"<<'\n';
return 0;
}


MaratonIME goes to the movies

Description:
Better than “Fifth Wave”
in the World, Everyone
Believe it if you can, studies show that we in MaratonIME live not only out of competitive programming.

In a saturday, after taking part in a virtual contest, our heroes decide to enjoy the afternoon watching a movie session. But they didn’t choose any movie, but an n-D movie, that is, a movie with n dimensions.

During a chase scene, the main character jumps over a chain in the parking lot. Of course this was done in a very athletic way, and for some reason that drove Yan, one of the competitive programmers, mad.

“Hollywood makes everything seem easy, but jumping over a chain is really hard!”

The rest of the crowd, after the movie, argued with Yan that the actor surely jumped over the chain, but Yan disagreed, saying that it was done by some camera trick or by special effects.

To prove his point, he bought another ticket for the movie and this time he took highly precise measuring instruments to the session. Yan’s plan was to show that the distance from the actor’s foot to the floor was smaller than the distance from the chain to the floor, and that would prove that the actor didn’t actually jump over the chain.

But math in n dimensions is hard. Everyone knows that distance in the 2D plane between two points (x0, y0) and (x1, y1) is given by the formula

Most people also know that distance between two points (x0, y0, z0) e (x1, y1, z1) in 3D space is given by the formula

Both formulas describe the euclidean distance, in the 2 and 3 dimensional case. Your task is, given three points in an n dimensional space, tell if the the closest ones are the foot and the floor or the chain and the flooor, according to euclidean distance.

Input

The input begins with an integer n, followed by three lines, each with the representation of a point in an n-dimensional space.
Dimensions confuse us, humans, so you can assume that 1 ≤ n ≤ 1e5.
The second line represents the coordinates of the floor, and contains n integers a1, …, an.
The third line represents the coordinates of the foot of the main character, and contains n integers b1, …, bn.
The fourth line represents the coordinates of the chain, and contains n integers c1, …, cn.
The movie theather is not arbitrarily large, so you can assume that the absolute value of these coordinates are not greater than 1e4.

Output

Print who wins the argument, that is, print “Yan” if the distance between the floor and the foot is not greater than the distance between the floor and the chain, or “MaratonIME” otherwise.

Examples
Input

2
0 0
1 1
2 2

Output

Yan

Input

4
0 0 0 0
2 2 2 2
1 1 1 1

Output

MaratonIME

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
const int sijia = 211314;
typedef long long ll;
ll f[sijia],m[sijia],gj[sijia];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)    cin>>f[i];
for(int i=0;i<n;i++)    cin>>m[i];
for(int i=0;i<n;i++)    cin>>gj[i];
double x,y;
x=y=0;
for(int i=0;i<n;i++)
{
x+=(m[i]-f[i])*(m[i]-f[i]);
y+=(gj[i]-f[i])*(gj[i]-f[i]);
}
if(x<=y)
puts("Yan");
else    puts("MaratonIME");
}


MaratonIME goes to a japanese restaurant

Description:
Matsu?
Member, MaratonIME’s
Nathan and Yan are very dedicated programmers. They apply their knowledge in algorithms in problems beyond the programming competitions themselves, optimizing even the most trivial every day things.

Some question if they aren’t just crazy, and if it wouldn’t be better to just do what has to be done.

Anyhow, eventually some conflicts happen when their approaches differ about what has to be done. That always happens when they decide to go to japanese restaurants.

Everybody knows that the objective in an all-you-can eat it to try to eat many distinct kinds of food. Nathan and Yan differ in opinions on how to achieve that. Both competitors, when sitting to eat an asian delicacy, eat until nothing is left on their plates.

The difference is that Yan, respecting the wisdom of the nipponic masters, eats in the order the food arrives, whereas Nathan claims that the food is better the latter it arrives, to spare the most expensive ingredients, and so asks that his plates come in inverted order.

Given the default order the dishes will arrive and the time Nathan and Yan will stay at the restaurant, determine who is going to eat the most different kinds of food, or if both ate the same number of different kinds of food, given that Yan eats the food in order and Nathan in inverted order.

Input

The first line of input has two integers: 0 < n ≤ 1e5, how many plates will be served and 0 < T ≤ 1e6, how long (in minutes) Yan and Nathan will stay at the restaurant.
In the following line, n integers 0 < ti ≤ 1e3, ti is how long it takes to eat the i-th dish (in minutes).
The restaurants are very well administrated, so you can assume that when one of the competitors finishes his dish, the following dish is already on the table.

Output

If Yan is going to taste more dishes than Nathan, print “Yan”. If Nathan is going to taste more dishes than Yan, print “Nathan”. Otherwise, if we have a tie, print “Empate”.

Examples
Input

10 45
1 2 3 4 5 6 7 8 9 10

Output

Yan

Input

10 45
10 2 3 4 5 6 7 8 9 1

Output

Nathan

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[211314];
int main()
{
ll n,m;
cin>>n>>m;
for(ll i=0;i<n;i++)
cin>>a[i];
ll x,y,s1=0,s2=0;
x=m,y=m;
for(ll i=0;i<n;i++)
{
if(x>=a[i])
{
x-=a[i];
s1++;
}
else    break;
}
for(ll i=n-1;i>=0;i--)
{
if(y>=a[i])
{
y-=a[i];
s2++;
}
else break;
}
if(s1>s2)    puts("Yan");
else if(s1<s2)    puts("Nathan");
else    puts("Empate");
}


MaratonIME goes to the japanese restaurant (again)

Description:
Nakato?
from MaratonIME, Members
After a long day of hard training, MaratonIME (マラトニメ) members decided to go to a Japanese restaurant. Yeah, we love Japanese food.

After a lot of sushi boats, when everyone was more than satisfied, they asked the sushi-man Sussushi (ススシ) for the last boat. Sussushi felt challenged and answered:

– You want one more boat? You shall have one more boat…

The sushi boat that he brought was the biggest that any contestant had ever seen. Some contestants even dare saying that was the biggest sushi boat that ever existed, exceeding the previous limit of 105 sushis made by the suhiwoman Gioza (ジョザ) in 742, in a festival for the king that year, Carlos-sama (カーロス様).

Besides that the contestants accepted the challenge, and together they managed to eat all the sushis. After that, the contestants we’re so full that they couldn’t touch each other. They couldn’t even think about programming problems. Help them find what pair of friends are touching themselves, so they can move away from each other.

The contestant are represented as circles in plane, and two contestants touch each other if the circles touch each other. It’s guaranteed that the intersection area of any two circles is null.

Input

In the first line there is a single integer, n indicating the number of contestants (2 ≤ n ≤ 1000).
Each one of the next n lines has 3 integers xi, yi e ri, the (i + 1)-th line describes the ith contestant. (xi, yi) are the coordinates of the center of the circle, and ri is the radius. ( - 1e4 ≤ xi, yi ≤ 1e4, 1 ≤ ri ≤ 2·1e4)
It is guaranteed that the intersection area of any two circles is null.

Output

For each pair of circles that touch each other, print in one line the indexes of these circles. The collisions can be printed in any order, the indexes of both circles can also be printed in any order.
Don’t print the collisions more than once, that means, if i intersects with j, print i j or j i, but not both.

Example
Input

3
0 0 2
5 0 3
10 10 1

Output

1 2

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,r;
}a[1314];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y>>a[i].r;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(sqrt((a[j].y-a[i].y)*(a[j].y-a[i].y)+(a[j].x-a[i].x)*(a[j].x-a[i].x))<=(a[i].r+a[j].r))
cout<<i <<" "<<j<<endl;
}
}
return 0;
}


MaratonIME goes to the karaoke

Description:
♬ Hit me, lock me up, do anything with me, … ♬
and Marrone, Bruno
After thousands of years repeating the title of this problem statement, always with an excited and inviting tone, Nathan finally persuaded his colleagues to go to the karaoke. He is feeling radiant with this achievement.

But there is a problem. After so much time trying to make his friends go to the karaoke, Nathan is afraid of embarrassing himself when he goes to sing the following classics of Brazilian music:

Waitress – Reginaldo Rossi
Blue Nightclub – Joaquim and Manuel
Paper Heart – Sérgio Kings
Love Bubble – Fagner
You did not teach me to forget – Fernando Mendes
To avoid the humiliation, and to not discourage his fellows in future hang outs at the karaoke, Nathan decided to print all the song’s ciphers that are available in the karaoke, to check while he sings. However, this resulted in a colossal amount of paper, that he is not able to carry.

But the perseverance and ingenuity of an envious programmer is not something you should underestimate.

Nathan realized that, after all, there were only 7 musical notes. The specialists in this matter used to represent this notes with the letters A, B, C, D, E, F and G. Even more, it’s common that the same note appears several times in sequence. He decided then, to compress the songs, changing every occurrence of repeated notes with the note followed by how many times it occurs.

For instance, given the sequence

[(A,A,A,B,B,B,C,G,G,G,G,G,G,G,G,G,G,G)] the compressed version is [A3B3C1G11]

Unfortunately, Nathan also needs to pack his floral suit and to comb his beard – two homeric jobs – and he is out of time to compress the notes. Help him to not embarrass himself by writing a program that can solve this task.

Input

Each input consist of a single line, a sequence of caracteres S such as |S| ≤ 105, formed only by the letters A, B, C, D, E, F and G.

Output

For each input, print in a single line, such as each sequence of similar notes are replaced by the note that occurs and how many times it occurs, as showed in the example.

Examples

Input

ABBGA

Output

A1B2G1A1

Input

AAABBBCGGGGGGGGGGG

Output

A3B3C1G11

Problem solving:

Code:

#include<cstdio>
#include<string>
#include<iostream>
const int xiaozhu=1e5+10;
struct node{
char s;
int ti;
}sijia[xiaozhu];
using namespace std;
int main()
{
string s;
cin>>s;
sijia[0].s=s[0];sijia[0].ti=1;
int pos=0;
for(int i=1;i<s.size();i++)
{
if(s[i]==sijia[pos].s)
{
sijia[pos].ti++;
}
else
{
pos++;
sijia[pos].s=s[i];
sijia[pos].ti=1;
}
}
for(int i=0;i<=pos;i++)
{
cout<<sijia[i].s<<sijia[i].ti;
}
return 0;
}


MaratonIME goes karting

Description:
Yan, it’s red!!!
desperate, Passengers
Once after a contest, the competitive programmers were sad because of bad results. Seeing the situation, Renzo, MaratonIME’s coach, suggested they should do something fun to relax. After a big discussion, they decided to go karting. Looking for a place that was viable to all students, they found Kartforces, a kart track near Cidade Universitária. However, the track was too small and only fitted two racers by race. As passionate competitive programmers, they organised a fair tournament where everyone raced against everyone, two by two, only once. In each race, the winner got one point on the scoreboard. Draws were allowed and no one scored in this case. The winner was the biggest scorer. There were N competitive programmers present and:

Each competitive programmer had a skill hi.
If hi > hj where 1 ≤ i, j ≤ N and i ≠ j, then the competitive programmer i won the race against j.

Input

The first line consists on a single integer N, the number of competitive programmers. The second line contains N integers hi, the skill of the i - th competitive programmer.
1 ≤ N ≤ 1e5
0 ≤ hi ≤ 1e9

Output

The output consists in a single integer i, the champion competitive programmer. If it’s not possible to determine the champion, print  - 1.

Example

Input

3
2 4 6

Output

3

Problem solving:

Code:

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node{
ll x,id;
}a[100005];
bool cmp(node a,node b)
{
return a.x>b.x;
}
int main()
{
ll n;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].x);
a[i].id=i;
}
for(int i=1;i<n;i++)
{
if(a[i].x==a[i+1].x)
{
puts("-1");
return 0;
}
}
sort(a+1,a+n+1,cmp);
printf("%lld\n",a[1].id);
}


MaratonIME returns home

Description:
♬ Renzo, they’re calling. Renzo, pick up the phone ♬
Ringtones, Top
Popular among the most traditional coders, the Summer Camp is famous for its fancy parties. After each party all attendees must return to their homes, but the way back home is not always easy: mildly drunk coders walk weird and often find or lose money along the way. However, MaratonIME always has a sober member in the group, who assures no one will lose money, except when they are robbed.

On its way back MaratonIME knows that they can call their coach, Renzo, who will pick them up immediately. Instead of doing that right after the party, they want to know what is the maximum amount of money they can carry back to their homes.

Your task is to write a program that solves this problem. Consider the following facts:

The city map can be seen as an N by M grid;
Members of MaratonIME are initially at the top left corner, and start walking right, carrying no money;
Whenever they reach the end of a row, they walk to the row below and start walking in the opposite direction (if they were walking right, they walk left the next row, and vice-versa);
They cannot go past the last row;
Whenever they meet a burglar, they lose all their money;
They can call Renzo at anytime, and he will pick them up instantly.
Input

The first line of the input contains two integers N and M (1 ≤ N, M ≤ 103), respectively, the number of rows and columns of the grid. Then follows N lines, each containing M characters, representing the city map. Each cell of the city map can be either:
, _ meaning there is nothing at this cell of the grid;
, ‘.’ meaning there is a coin worth 1 unit of money at this cell;
, ‘L’ meaning there is a burglar at that cell.

Output

The output must contain a single integer: the maximum amount of money MaratonIME can carry back home.

Example
Input

3 3
__.
_._
L._


Output

2

Note

In the example above, MaratonIME follows the following path: (1, 1) (1, 2) (1, 3) (2, 3) (2, 2) (2, 1) (3, 1) (3, 2) (3, 3). When they reach (2, 2) or (2, 1) they will have 2 coins, and that is the highest value they can get before calling Renzo.

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
const int xiao =1314;
const int zhu =1314;
char sijia[xiao][zhu];
int n,m,ans,flag;
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
scanf("%s",sijia[i]);
string s;
for(int i=0;i<n;i++)
{
if(i%2==0)
{
for(int j=0;j<m;j++)
s+=sijia[i][j];
}
else
{
for(int j=m-1;j>=0;j--)
s+=sijia[i][j];
}
}
int now=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='.')    now++;
if(s[i]=='L')    now=0;
ans=max(ans,now);
}
cout<<ans<<endl;
}