Algorithmia IIITN 2024 - Round 1
A. Phoenix Against the Monsters
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Phoenix, a skilled warrior, has been assigned an important mission: to deliver critical information from the city of Nagpur to the stronghold of Mumbai. The journey is filled with danger, as monsters guard the roads connecting different cities. Each road has a certain number of monsters that Phoenix will need to fight.

Phoenix has a special ability that he can use once during his journey. This ability allows him to halve the number of monsters (rounded down to the nearest whole number) on either one road or two consecutive roads. By using this ability wisely, Phoenix can reduce the total number of monsters he has to fight and increase his chances of completing the mission.

Your task is to help Phoenix find the minimum total number of monsters he must face to deliver the information to Mumbai.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$ and $$$1 \leq m \leq 2 \cdot 10^5$$$): the number of cities and the number of roads connecting them. The cities are numbered $$$1,$$$ $$$2,$$$ $$$\ldots$$$ $$$n$$$. City $$$1$$$ is Nagpur, and city $$$n$$$ is Mumbai.

After this, there are $$$m$$$ lines describing the roads. Each line contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \leq u, v \leq n$$$ and $$$1 \leq w \leq 10^9$$$): a road starts at city $$$u$$$, ends at city $$$v$$$, and has $$$w$$$ monsters on that road. Each road is unidirectional.

You can assume that it is always possible to get from Nagpur to Mumbai.

Output

Output a single integer — the minimum total number of monsters Phoenix must face to deliver the information from Nagpur to Mumbai.

Examples
Input
5 6
1 2 5
2 3 2
3 5 1
1 4 10
4 5 5
2 4 3
Output
4
Input
2 1
1 2 5
Output
2
Input
6 8
1 2 7
1 3 4
2 4 3
2 5 2
3 4 6
4 6 2
5 6 4
3 5 8
Output
6
Note
  • In the first sample, Phoenix starts in City $$$1$$$ (Nagpur).
  • He takes the road to City $$$2$$$, which has $$$5$$$ monsters.
  • He then proceeds from City $$$2$$$ to City $$$3$$$, where the road has $$$2$$$ monsters.
  • From City $$$3$$$, he travels to City $$$5$$$ on a road with only $$$1$$$ monster.
  • Phoenix uses his special ability to halve the number of monsters on the roads between City $$$1$$$ and City $$$2$$$, and City $$$2$$$ and City $$$3$$$, reducing the monsters to $$$2$$$ and $$$1$$$ respectively.
  • This results in a total of $$$4$$$ monsters he must fight to deliver the information to City $$$5$$$ (Mumbai).
  • In the second sample, Phoenix must travel directly from City $$$1$$$ (Nagpur) to City $$$2$$$ (Mumbai) on a road with $$$5$$$ monsters. He uses his ability to halve the monsters on this road, reducing the count to $$$2$$$. Thus, Phoenix only faces $$$2$$$ monsters in total.

B. Spidey and the Palindrome Sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Thanos, the most feared villain in the universe, had conquered countless worlds. But there was one secret, one weakness that haunted him: the Palindrome Sequence. A mysterious force, ancient and powerful, had once foretold that a properly formed sequence of palindromes could undo his cosmic power.

Spidey stumbled upon this knowledge during a secret mission. He learned that the only way to shatter the invincibility of Thanos was to create a palindrome sequence. Since he was always out of school, he needs your help to defeat Thanos.

You are given a string $$$s$$$ of length $$$n$$$ containing lowercase letters.

A palindrome sequence is a sequence containing only palindromes of size $$$m$$$ $$$(m\ge2)$$$ and has at least $$$2$$$ palindromes. (All palindromes are of equal size)

Your task is to determine whether or not it is possible to defeat Thanos by creating a palindrome sequence by re-arranging the given string and if so, create a palindrome-sequence.

Input

The first line contains a single integer $$$t$$$ $$$(1\le t \le 10^4)$$$ — the number of testcases.

The only line of each testcase contains the string $$$s$$$ of size $$$n$$$ $$$(1\le n\le2\cdot10^5)$$$. Sum of $$$n$$$ over all testcases does not exceed $$$2\cdot10^5$$$.

Output

For each testcase,

If possible,

  • Output two lines, the first line contains a single integer $$$m$$$ — the size of each palindrome in the sequence.
  • The second line contains the palindrome sequence obtained after re-arranging the given string $$$s$$$.

If not possible, output $$$-1$$$.

Example
Input
5
abbcca
abcabcabc
dotslash
racecar
deed
Output
2
ccaabb
3
bbbcccaaa
-1
-1
2
eedd
Note
  • In the first testcase, we can have a palindrome-sequence of $$$3$$$ palindromes i.e. aa, bb and cc. Hence, we first output the size of each palindrome, $$$2$$$ and then the palindrome-sequence ccaabb.
  • The second and fifth testcase is similar to the first testcase.
  • In the third and fourth testcase, there is no possible palindrome-sequence.

C. Reduce or Divide
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a reverse binary string of a number $$$n$$$.

Alice and Bob are playing a game.

The play starts with the number $$$n$$$. In each turn a player can choose any one of the following moves:

  • Reduce $$$1$$$ from $$$n$$$, if $$$n$$$ is a positive integer.
  • Choose an odd number that is the divisor of $$$n$$$ and greater than $$$1$$$ and divide $$$n$$$ by that number.

The player who is unable to play wins the game.

Bob starts the game. Determine the winner if both Alice and Bob play optimally.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10_{}^3)$$$ – the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$x$$$ $$$(1 \le x \le 34)$$$ — the length of binary string.

The second line of each test case contains a reverse binary string of $$$n$$$.

Output

For each test case print single world in a new line:

  • "ALICE" if Alice wins the game,
  • "BOB" if Bob wins the game,
  • "DRAW" if the game ends in a draw.

Note that the output is case sensitive.

Example
Input
3
2
11
3
001
3
101
Output
BOB
ALICE
BOB
Note
  • In the first test case, after reversing the string and converting that binary to decimal the number is $$$n = 3$$$. Bob divides $$$n$$$ by $$$3$$$ in the first move. Now $$$n = 1$$$, Alice subtracts $$$1$$$ in the second move. Now $$$n = 0$$$, Bob cannot make a move, so he wins the game.
  • In the second test case, after reversing the string and converting that binary to decimal the number is $$$n = 4$$$. Bob subtracts $$$1$$$ in the first move. Now $$$n = 3$$$, Alice divides $$$n$$$ by $$$3$$$ in the second move. Now $$$n = 1$$$, Bob subtracts $$$1$$$ in the third move. Now $$$n = 0$$$, Alice cannot make a move, so he wins the game.
  • In the third test case, after reversing the string and converting that binary to decimal the number is $$$n = 5$$$. Bob divides $$$n$$$ by $$$5$$$ in the first move. Now $$$n = 1$$$, Alice subtracts $$$1$$$ in the second move. Now $$$n = 0$$$, Bob cannot make a move, so he wins the game.

D. Harsh and profits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Harsh has started a business of trading scrap along with his friend. The profit he makes on day $$$1$$$ is $$$0$$$, on day $$$2$$$ is $$$1$$$, on day $$$3$$$ is $$$3$$$, on day $$$4$$$ is $$$6$$$, on day $$$5$$$ is $$$10$$$. More formally, the increment in Harsh's profit increases by one every day.

Harsh has a girlfriend, and he goes to her father to ask for permission for the marriage. Her father wants to know how much money Harsh made that day. Harsh is stressed and asks for your help to find his profit today.

Help him with the calculation of the profit if he asks for marriage on the $$$d$$$th day.

Input

The first line will contain the integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — The number of test cases.

The next $$$t$$$ lines will each contain a single integer $$$d$$$, where $$$(1 \le d \le 10^9)$$$ — The current number of days.

Output

For each test output a single integer — The profit on the $$$dth$$$ day.

Example
Input
3
5
6
3
Output
10
15
3

E. Magical Coins
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a magical land, the currency is based on certain $$$denominations$$$. These $$$denominations$$$ (coins) are of the order $$$11,111,1111,11111,...$$$ and so on.

Gopal has bought an item, determine if it is possible for him to pay with the help of these coins.

He can use any coin $$$any$$$ number of times.

Input

The input consists of multiple test cases.

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — The number of test cases.

Each test case $$$t$$$ contains a single integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — Cost of the item.

Output

For each test case, output YES if it is possible to pay, otherwise output NO.

Example
Input
3
33
144
69
Output
YES
YES
NO
Note

For $$$n = 33$$$, Gopal can use three coins of $$${11}$$$ ,so the output is YES.

For $$$n = 144$$$, Gopal can use one $$$\textbf{coin}$$$ of $$${111}$$$ and three coins of $$${11}$$$ to make 144, so the output is YES.

For $$$n = 69$$$, no combination is possible, so the output is NO.

F. Oddly Even Challenge
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the world of Dr. Numerus, machines communicate using special codes that follow a strict rule: the digits of a number must follow a specific pattern. Odd digits must appear at odd indices, and even digits must appear at even indices (indices are 1-based). Given a number $$$N$$$, your task is to determine how many numbers from $$$0$$$ to $$$N$$$ follow this pattern.

Input

The only line contains single integer $$$N$$$ $$$(1 \le N \le 10^{18})$$$

Output

Print a single integer — the number of valid numbers between $$$0$$$ and $$$N$$$ that have odd digits at odd indices and even digits at even indices.

Examples
Input
12
Output
7
Input
38
Output
15
Input
9724
Output
755
Note

The possible numbers for $$$N = 12$$$ are $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$, $$$9$$$, $$$10$$$ and $$$12$$$

G. Odd Non Primes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Roshan has devised an intriguing card game for his friends Gopal and Vasu. He presents them with a deck of cards, each labeled with an integer, and challenges them to find the maximum value of a special expression based on the cards in any sub-deck. The value of special expression of a sub-deck is determined using the following rule:

  • (Number of odd numbered cards) − (Number of prime numbered cards)

A sub-deck is any contiguous sequence (containing atleast 1 card) of cards drawn from the original deck. Gopal and Vasu must find the sub-deck that maximizes the value of this expression. While Gopal thinks about calculating the value for each possible sub-deck, Vasu suspects there might be a more efficient way to figure it out.

Can you help them determine the highest value of special expression?

Input

Each test contains multiple test cases. The first line contains a single integer t $$$(1 \le t \le 10_{}^3)$$$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer n $$$(1 \le n \le 10_{}^3)$$$  — the number of cards.

The second line of each test case contains n integers $$$a_1 , a_2 , ... , a_n$$$ $$$(1 \le a_i \le 10_{}^6)$$$  — the number of cards of type i, for each $$${1 \le i \le n}$$$ .

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10_{}^3$$$.

Output

For each test case, output a single integer — the maximum possible value of the special expression.

Example
Input
5
6
1 2 3 4 5 6
8
5 7 3 8 3 9 10 1
6
6 3 3 3 5 5
6
5 6 4 1 4 5
9
8 6 4 2 1 3 5 7 9
Output
1
2
0
1
2
Note

In the first testcase, the maximum possible value of the special expression is when we only select the first card.

In the third testcase, the maximum possible value of the special expression is when we select the subdeck starting at third and ending at fourth card.

In the last testcase, the maximum possible value of the special expression is when we select the subdeck starting at fifth and ending at ninth card $$$1,3,5,7,9$$$.

H. AI Takeover
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We are in the year, 2050 and AI has advanced to a whole new level. AI is planning to take over humans but needs to communicate with one another without human interception. To do so they decide to create a language of their own.

There are many levels of AI bots from level-1 to level-$$$n$$$.

The bots perform the following tasks:

  • A level-1 bot creates a new word.
  • A level-$$$n$$$ bot creates a level-($$$n$$$-1) bot. $$$(n \neq 1)$$$.
It takes them 5 minutes to do a task. Initially you have $$$k$$$ $$$(1\le k \le 10^9)$$$ level-$$$n$$$ $$$(1\le n\le 100)$$$ bots.

Spidey being the savior he is, decides to learn this language to stop AI. How many words will he have to learn to stop them if $$$t$$$ $$$(1\le t \le 10^4)$$$ minutes have passed?

Input

The only input line consists of three integers $$$n$$$ $$$(1\le n\le 100)$$$ — Highest level of the bots, $$$k$$$ $$$(1\le k \le 10^9)$$$ — Initial number of level-$$$n$$$ bots and $$$t$$$ $$$(1\le t \le 10^4)$$$ — Time passed.

Output

Output a single integer — The number of words Spidey has to learn after $$$t$$$ minutes have passed. Since the answer can be huge, output it modulo $$$10^9 + 7$$$.

Examples
Input
5 10 40
Output
560
Input
40 100 50
Output
0
Input
10 10 100
Output
1847560
Note

In testcase 1 we have level-5 bots.

  • At 5 minutes we have 10 level-5 and 10 level 4 bots.
  • At 10 minutes we have 10 level-5, 20 level-4 and 10 level-3 bots.
  • At 15 minutes we have 10 level-5, 30 level-4, 30 level-3 and 10 level-2 bots.
  • At 20 minutes we have 10 level-5, 40 level-4, 60 level-3, 40 level-2 and 10 level-1 bots.
  • At 25 minutes we have 10 level-5, 50 level-4, 100 level-3, 100 level-2, 50 level-1 bots and 10 words.
  • At 30 minutes we have 10 level-5, 60 level-4, 150 level-3, 200 level-2, 150 level-1 bots and 60 words.
  • At 35 minutes we have 10 level-5, 70 level-4, 210 level-3, 350 level-2, 350 level-1 bots and 210 words.
  • At 40 minutes we have 10 level-5, 70 level-4, 280 level-3, 560 level-2, 700 level-1 bots and 560 words.
In testcase 2, we have level-40 bots. To reach the creation of new words we need at least 200 minutes.