Asu Coding Cup 4
A. Bashar and SHAWERMA!
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bashar Loves SHAWERMA sandwiches very much, so he decided to buy some sandwiches.

The price of one sandwich is 2 JDs and Bashar wants to eat $$$x$$$ sandwiches.

how many JDs Bashar needs to buy the $$$x$$$ sandwiches?

Input

The input contains a single integer $$$x$$$ $$$(1 \leq x \leq 30 )$$$ .

Output

Print the number of JDs Bashar needs to buy the $$$x$$$ sandwiches.

Example
Input
17
Output
34

B. Calculate The Area
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mahmoud bought a rectangular shaped land, it's area was $$$n$$$ $$$units^2$$$.

His best friend Ayoub asked him to calculate the height and the width of the land.

Mahmoud hates math, can you help him to calculate the height and the width of the land?

If there are multiple solutions print any of them.

Input

The input contains single integer $$$n$$$ , $$$(1 \leq n \leq 200)$$$ represent the area

Output

Print two integers that represent the height and the width of the rectangle, if there are multiple solutions print any of them.

Examples
Input
20
Output
4 5
Input
16
Output
4 4
Input
6
Output
2 3
Note

area = height*width

C. The Ending Point
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tahhan was hungry, so AbuTahun decided to show him the way to Rakan's cafeteria.

AbuTahun gave Tahhan a string consisting only of the letters ('L','R','U','D'), denotes the path to the cafeteria.

  • U — move from $$$(x,y)$$$ to $$$(x,y+1)$$$.
  • D — move from $$$(x,y)$$$ to $$$(x,y-1)$$$.
  • L — move from $$$(x,y)$$$ to $$$(x-1,y)$$$.
  • R — move from $$$(x,y)$$$ to $$$(x+1,y)$$$.

Tahhan located at point $$$(x,y)$$$, and he wants to go to the cafeteria.

Can you tell Tahhan where Rakan's cafeteria is?

Input

first line of input consists of two integers $$$x,y$$$ $$$(1 \leq x,y \leq 100)$$$ , denotes the starting point.

the second line consists of string $$$s$$$ $$$(1 \leq |s| \leq 100)$$$ denotes the path to the cafeteria .

Output

print two integers which denotes the ending point.

*Note* the answer could contains a negative integer.

Example
Input
5 3
UUUDLRLRLRR
Output
6 5

D. Bashar and the bad land (Easy)
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between easy and hard versions is constraints.

Bashar is trapped in an abandoned city and he wants to escape. In order to escape, he has to pay $$$x$$$ golden coins. So he decided to collect the gold in the houses of that city. The city contains $$$n$$$ houses aligned in a straight line. Each house contains $$$a_i$$$ coins of gold.

Help Bashar to find the shortest distance he has to walk until he collects the needed amount of golden coins to get away.

Note Bashar can start from any house and stop at any house.

Input

First line of input contains two integers $$$x$$$, and $$$n$$$, $$$(1 \leq n \leq 1000 , 1\leq x \leq 10^{6})$$$ The needed amount of gold until Bashar can get away, and The number of houses in the city.

The second line of input contains $$$n$$$ integers $$$a_i$$$, $$$(1 \leq a_i \leq 1000)$$$ the amount of gold in the $$$i^{th}$$$ house.

Output

Print a single represents the minimum distance Bashar has to walk until he reach The needed amount of golden coins, if he can't reach The needed amount of golden coins print -1.

Examples
Input
5 12
1 3 4 5 2
Output
3
Input
5 13
5 1 2 3 4
Output
5
Input
5 6
1 1 1 1 1
Output
-1
Note

In the first example, Bashar walked from $$$2^{nd}$$$ house to the $$$4^{th}$$$ house to collect 12 coins (3+4+5=12), so the distance is 3.

E. Bashar and the bad land (Hard)
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between easy and hard versions is constraints.

Bashar is trapped in an abandoned city and he wants to escape. In order to escape, he has to pay $$$x$$$ golden coins. So he decided to collect the gold in the houses of that city. The city contains $$$n$$$ houses aligned in a straight line. Each house contains $$$a_i$$$ coins of gold.

Help Bashar to find the shortest distance he has to walk until he collects the needed amount of golden coins to get away.

Note Bashar can start from any house and stop at any house.

Input

First line of input contains two integers $$$x$$$, and $$$n$$$, $$$(1 \leq n \leq 10^{5} , 1\leq x \leq 10^{9})$$$ The needed amount of gold until Bashar can get away, and The number of houses in the city.

The second line of input contains $$$n$$$ integers $$$a_i$$$, $$$(1 \leq a_i \leq 10^{5})$$$ the amount of gold in the $$$i^{th}$$$ house.

Output

Print a single represents the minimum distance Bashar has to walk until he reach The needed amount of golden coins, if he can't reach The needed amount of golden coins print -1.

Examples
Input
5 12
1 3 4 5 2
Output
3
Input
5 13
5 1 2 3 4
Output
5
Input
5 6
1 1 1 1 1
Output
-1
Note

In the first example, Bashar walked from $$$2^{nd}$$$ house to the $$$4^{th}$$$ house to collect 12 coins (3+4+5=12), so the distance is 3.

F. Weird Game
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Some day Bashar and Mahmoud felt hungry so they decided to play a game with food.

Ayoub made $$$n$$$ cup cakes for Bashsar and Mahmoud.

So the game goes as follow, each player can do one of these actions alternatively :

  1. eat 1 cup cake (so the number of cup cakes will be subtracted by 1).
  2. eat exactly half of the cup cakes (if the number of cup cakes is even number).

If the number of cup cakes is equals to 1 the current player loses.

If Mahmoud starts, and each player played optimally, print the name of the winner!

Input

the input contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^{9})$$$

Output

Print 'Mahmoud' if Mahmoud wins, print 'Bashar' otherwise.

(Without the quotes)

Examples
Input
4
Output
Mahmoud
Input
3
Output
Bashar
Note

In first sample:

In first step the number of cup cakes is 4 and it's Mahmoud turn, Mahmoud decided to eat one cup cake so the remaining cup cakes are 3.

Then Bashar can only eat one cup cake so the remaining cup cakes are 2.

Mahmoud eats one cup cake and the remaining is only 1 cup cake.

It's Bashar's turn and there is only one cup cake, so Bashar loses.

G. Super Weird Game
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bashar and Mahmoud felt bored so they decided to play another game.

In this game each player has an array of size $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ consists of elements of values between 1 and $$$10^5$$$.

Ayoub thinks that the pair $$$(i, j)$$$ is a good pair if all of the following conditions hold:

  1. i < j.
  2. $$$a_i$$$ + $$$a_j$$$ = $$$k$$$.

The player who has the greater number of good pairs wins.

If you know the value of $$$k$$$, and the value of the elements in Bashar's and Mahmoud's array, can you determine the winner ?

Input

The first line of input contains 2 integers $$$n$$$, $$$k$$$, $$$(1 \leq n,k \leq 10^5)$$$, which denotes the size of the arrays Ayoub's random number.

The Second line of input contains $$$n$$$ integers $$$m_1$$$,$$$m_2$$$,...,$$$m_n$$$ $$$(1 \leq m_i \leq 10^5)$$$, denotes Mahmoud's array.

The Tired line of input contains $$$n$$$ integers $$$b_1$$$,$$$b_2$$$,...,$$$b_n$$$ $$$(1 \leq b_i \leq 10^5)$$$, denotes Bashar's array.

Output

if Mahmoud wins print $$$"Mahmoud"$$$, if Bashar wins print $$$"Bashar"$$$, otherwise print $$$"Draw"$$$.

Example
Input
7 3
1 1 2 3 4 1 2
2 2 2 1 1 1 2
Output
BASHAR

H. Mahmoud and the flagstones
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

When Mahmoud was walking in BetaCity, he saw a sequence of $$$n$$$ flagstones each one of them has a color $$$a_i$$$.

Mahmoud hates different things, so he asked Ayoub to count the number of ways to choose a nonempty subsets of flagstones such that the color of all flagstones in the subset is the same.

Ayoub is very lazy, and he notice that the number of subsets is very large, so he needs your help.

print the number of nonempty subsets of flagstone that have the same color.

As this number may be too large, print it modulo $$$10^{9}$$$ + 7.

Input

First line of input contains integer $$$n$$$ $$$(1 \leq n \leq 10^5 )$$$, the length of the sequence.

The second line contains $$$n$$$ integers $$$ a_1 , a_2 , ... , a_n $$$ $$$(1 \leq a_i \leq 100000)$$$, each of them denotes the color of the $$$i^{th}$$$ flagstone.

Output

print the number of nonempty subsets of flagstone that have the same color modulo $$$10^{9}$$$ + 7.

Example
Input
5
3 5 5 1 2
Output
6
Note

in the example, the subsets are:

{$$$a_1$$$} —> {$$$3$$$}

{$$$a_2$$$} —> {$$$5$$$}

{$$$a_3$$$} —> {$$$5$$$}

{$$$a_4$$$} —> {$$$1$$$}

{$$$a_5$$$} —> {$$$2$$$}

{$$$a_2,a_3$$$} —> {$$$5,5$$$}

any other subset will have different colors.

I. Dr.Hjjawi and the MCQ
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dr.Hjjawi decided to make a special multiple choice questions exam MCQ.

for each question in the exam there is 5 answers (from $$$a$$$ to $$$e$$$) but only one of them is true.

After the exam, Dr.Hjjawi told his student that is the answer for all questions was the same letter (for example : all the correct answers are b), but without telling them what is the letter.

Ayoub was nervous after the exam, so he wants you to tell him what is the minimum number of true answers he would get, and the maximum number true answers he would get.

Input

The first line of input contains integer $$$n$$$ $$$(1 \leq n \leq 1000)$$$, denotes the number of questions.

The second line of input contains string $$$s$$$ of length $$$n$$$, the $$$i^{th}$$$ character of the string denotes Ayoub's answer for the $$$i^{th}$$$ question.

it is guaranteed that the string only consists of {'a','b','c','d','e'}.

Output

Print two integers, the minimum number of true answers, and the maximum number true answers.

Examples
Input
10
aaaaaabcde
Output
1 6
Input
3
aaa
Output
0 3

J. AbuTahun and Flash Memories
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

AbuTahun is preparing to ASU Coding Cup 4, and for unknown reasons he want to store all the solutions of the contestants in flash memories.

The contest is over, and there is $$$n$$$ solutions, all the solutions has the same size which is $$$x$$$ GB, and each flash memory could store at most $$$a$$$ GB.

Notice that you can't split one file and store it multiple memory, each file has to be stored in a single memory.

AbuTahun went to Rakan's store to buy some flash memories, can you tell him what is the minimum number of flash memories he has to by to store all the solutions?

Input

The input contains 3 integers $$$n$$$, $$$x$$$, $$$a$$$ $$$(1 \leq n \leq 10^5 )$$$ $$$(1 \leq x \leq a \leq 10^5 )$$$

Output

print the minimum number of flash memories ahmad has to buy.

Examples
Input
10 2 7
Output
4
Input
3 5 15
Output
1
Note

In first sample, there is 10 files each of them of size 2GB, and each flash memory could store at most 7GB so it could contains at most 3 files of size 2GB, so AbuTahun needs 4 flash memories to store 10 files of size 2GB.