RUCP x WiCS Mini-Contest
A. Sushi
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Templates for this problem are available here.

Alice and Bob are in a sushi eating contest. They have a tray of $$$n$$$ pieces. Alice starts by eating one piece. Bob, determined to keep up, follows suit by eating one piece. This process continues with Alice and Bob taking turns eating one piece until there are no more pieces of sushi left. Determine who will eat the last piece of sushi.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — the number of pieces of sushi.

Output

For each test case, output "Alice" if Alice eats the last piece of sushi or "Bob" if Bob eats the last piece of sushi (without quotes).

Example
Input
3
2
3
4
Output
Bob
Alice
Bob
Note

In the first test case, Alice eats the first piece of sushi and Bob eats the second, so Bob eats the last piece of sushi.

In the second test case, Alice eats the first and third pieces of sushi while Bob eats the second, so Alice eats the last piece of sushi.

B. Cursed Coins
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Templates for this problem are available here.

Alice the adventurer was doing a dungeon run when she encountered a room with $$$n$$$ locked chests, each chest filled with gold coins. Unfortunately, Bob, the evil wizard, cursed some of the chests, and now they contain cursed gold, which takes away from Alice's total coin count instead of increasing it. Alice has $$$k$$$ keys, which she may use to unlock up to $$$k$$$ chests.

You are given an array $$$a$$$, where $$$a_i$$$ represents the number of coins Alice will gain from opening the $$$i$$$-th chest. Note that if the $$$i$$$-th chest is a cursed chest, $$$a_i$$$ is negative.

What is the maximum amount of coins that Alice can end up with, assuming she uses her keys optimally? Alice does not need to use up all her keys, and her account balance starts at $$$0$$$ coins.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of chests and the number of keys, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$-100 \le a_i \le 100$$$) — the number of coins Alice will gain from opening the $$$i$$$-th chest.

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

Output

For each test case, output one integer — the maximum number of coins Alice can loot.

Example
Input
3
2 1
5 10
2 1
5 -10
3 3
1 -2 3
Output
10
5
4
Note

In the first test case, Alice can only choose one chest to open; thus, $$$10$$$ is the maximum number of gold coins that she can loot. In this case, Bob has not cursed any of the chests.

In the second test case, since Bob has cursed the 2nd chest, Alice can optimally open the 1st chest instead, yielding $$$5$$$ coins.

C. Six and Seven
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Templates for this problem are available here.

Alice loves the number "67". On her birthday, Bob gifts her a string $$$s$$$ consisting only of 6's and 7's. Alice is pleased, but she also wants to know how many ways she can choose one 6 and one 7 such that the 7 appears after the 6. Help her figure this out.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case contains a single string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$, where $$$|s|$$$ is the length of the string $$$s$$$), consisting only of characters 6 and 7.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one integer — the number of ways to choose one 6 and one 7.

Example
Input
4
767
677
6767
777
Output
1
2
3
0
Note

In the first test case, there is only $$$1$$$ way: choose the second and third characters.

In the second test case, there are $$$2$$$ ways: choose the first and second characters, or choose the first and third characters.

D. Stamina
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Templates for this problem are available here.

Alice is standing at position $$$1$$$ of a straight road and wants to reach position $$$n$$$. Initially, she has $$$0$$$ stamina. On each day, she can do exactly one of the following:

  • Walk forward from position $$$i$$$ to position $$$i + 1$$$ and lose $$$1$$$ stamina. She can only do this if she has at least $$$1$$$ stamina.
  • Rest at her current position $$$i$$$ and gain $$$a_i$$$ stamina.
What is the minimum number of days Alice needs to reach position $$$n$$$?
Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of positions on the road.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the amount of stamina Alice gains by resting at position $$$i$$$.

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

Output

For each test case, output one integer — the minimum number of days Alice needs to reach position $$$n$$$.

Example
Input
3
4
1 1 1 1
4
1 2 3 4
5
3 1 3 1 3
Output
6
5
6
Note

In the first test case, Alice can rest at position $$$1$$$ for the first $$$3$$$ days and walk forward for the next $$$3$$$ days.

In the second test case, Alice can do the following:

  1. Rest at position $$$1$$$. After this, her stamina is $$$1$$$.
  2. Walk to position $$$2$$$. After this, her stamina is $$$0$$$.
  3. Rest at position $$$2$$$. After this, her stamina is $$$2$$$.
  4. Walk to position $$$3$$$. After this, her stamina is $$$1$$$.
  5. Walk to position $$$4$$$. After this, her stamina is $$$0$$$.

E. Grid Coloring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Templates for this problem are available here.

Bob has an $$$n \times n$$$ grid of squares. Each square can be colored either red or blue. Bob is a fair person. He calls a grid "good" if every square is adjacent to exactly $$$2$$$ squares of the same color. Two squares are considered adjacent if they share a side.

Given an integer $$$n$$$, output a good coloring of an $$$n \times n$$$ grid or state that no good coloring exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

Each test case consists of a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the size of the grid.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print YES if there is a solution, and NO otherwise. You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes", and "YES" will all be recognized as positive answers).

If you printed YES, print $$$n$$$ additional lines. The $$$i$$$-th of these should contain $$$n$$$ characters R or B, indicating the colors of the squares in the $$$i$$$-th row of the grid in your coloring.

If there are multiple solutions, you may print any.

Example
Input
2
2
3
Output
YES
BB
BB
NO
Note

In the first test case, every square is adjacent to two squares of the same color. For example, $$$(1, 1)$$$ is adjacent to $$$(1, 2)$$$ and $$$(2, 1)$$$, and all of those squares are blue.

It can be shown that there is no good coloring of a $$$3 \times 3$$$ grid.