Operation Clydesdale 0
A. A Sorting Problem
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$[p[1], p[2], ..., p[n]]$$$ where all the numbers in the array are distinct. In addition, the numbers are positive integers between $$$1$$$ and $$$n$$$. You can only perform the following operations on the array: Pick two indices $$$x$$$ and $$$y$$$ such that $$$|p[x] - p[y]| = 1$$$, and then swap the values of $$$p[x]$$$ and $$$p[y]$$$. We now want to sort this array in ascending order. That is, to make $$$p[i] = i$$$ for all $$$i\in\{1,2,\dots,n\}$$$. For example, we can sort the array $$$[p[1]=2,p[2]=3,p[3]=1]$$$ in two operations:

  1. Swap $$$p[1]$$$ and $$$p[3]$$$. The array becomes $$$[p[1]=1,p[2]=3,p[3]=2]$$$.
  2. Swap $$$p[2]$$$ and $$$p[3]$$$. The array becomes $$$[p[1]=1,p[2]=2,p[3]=3]$$$ which is sorted in ascending order.

Please write a program to compute the minimum number of operations to sort a given array in ascending order.

Input

The input contain two lines. The first line contains one integer $$$n$$$. The second lines contain $$$n$$$ space-saparated numbers $$$p[1],p[2],\dots,p[n]$$$ representing the array $$$[p[1], p[2],\dots, p[n]]$$$

  • $$$1 \lt n\le 200000$$$.
  • $$$1\le p[i] \le n$$$.
  • All $$$p[i]$$$ are distinct.
Output

Output only one number that denotes the minimum number of operations required to sort the given array.

Examples
Input
3
1 3 2
Output
1
Input
5
5 3 2 1 4
Output
7

B. Animal Farm
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

On Animal Farm, the animals have rebelled against their human owner and have taken over the management of the farm. To ensure equality and fairness among all the animals, they have decided to create a new set of rules. However, as the new leaders, the pigs have started making changes to the rules to favor themselves.

The farm maintains a hierarchy of animals based on their species, with each animal assigned a specific influence level. This influence level, represented as a positive integer, determines the animal's priority in decision-making. Within a group, an animal can make decisions if it has the highest influence level among the members.

The pigs have a plan to maximize their collective influence in the leadership council by selecting a specific group of animals. Given a list of animals with their species and influence levels, you are tasked to form the most influential leadership council while adhering to the following rules:

  1. Only one pig species is allowed in the council to avoid power conflicts among the pigs.
  2. Every council member of non-pig species should have an influence level less than the influence level of the only pig's in the council.

Determine the maximum total influence levels of the council that can be formed under these rules.

Input

The first line contains an integer $$$n$$$, representing the number of animals. The next $$$n$$$ lines each contain a string species and a positive integer influence:

  • species is a string representing the species of the animal, e.g., "pig", "horse", "cow", etc.
  • influence is an integer representing the influence level of the animal.

Technical Specification

  • $$$1\le n\le 10^5$$$.
  • The length of species is at most $$$10$$$.
  • species consists of only English characters in lowercase.
  • At least one animal's species is pig.
  • influence is at most $$$10^8$$$.
Output

Output a single integer, the maximum total influence levels of the leadership council that can be formed following the rules.

Examples
Input
5
pig 10
horse 15
pig 5
cow 20
sheep 25
Output
10
Input
5
pig 10
horse 15
pig 15
cow 15
sheep 10
Output
25

C. Frisbee Training
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Competitive frisbee has, for some reason, become a thing now, and everyone's trying to be the best. For this reason, Johannes and Asfora have begun practicing this sport, and their practice routine goes something like this: both of them start at the same point, and Johannes throws the frisbee in some direction while Asfora begins running after the frisbee. They're intelligent, so when the frisbee is thrown, Asfora is able to precisely pinpoint where it's going to land and begins running towards that direction.

Since they've been training a lot, Asfora has gotten lazy and will now only run if he's certain that he'll reach the frisbee. He doesn't have time to do this calculation, so he asks you for help in knowing whether he'll run or not. When Johannes throws a frisbee, Asfora is able to tell you the coordinates in which it'll land in relation to the starting point, how fast he's able to run at that moment, and how long it takes for the frisbee to reach the ground. Will you be able to help him?

Input

The first line contains a single integer $$$T$$$, $$$(1 \leq T \leq 10^5)$$$ — the number of test cases.

Each test case is one line and contains four integers, $$$x$$$, $$$y$$$, $$$v$$$, $$$t$$$, $$$(1 \leq x, y \leq 10^4)$$$, $$$(1 \leq v, t \leq 10^2)$$$ — the $$$x$$$ and $$$y$$$ position where the frisbee lands in relation to the starting point, the speed in which Asfora runs, and the amount of time it took for the frisbee to reach the ground.

Output

For each test case, output YES if he can get to the frisbee in the elapsed time, or NO otherwise.

Example
Input
2
4 2 3 10
6 8 1 9
Output
YES
NO

D. Xor Sums
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Diego knows that the sum of all integers between $$$1$$$ and $$$N$$$ is $$$\frac{N(N+1)}{2}$$$. However, he is wondering how to compute the exclusive or of all integers between $$$1$$$ and $$$N$$$.

Exclusive or is also known as xor. Most programming languages represent it with the character ^.

Input

First, a single integer, $$$T$$$ $$$(1 \le T \le 10^5)$$$: the number of test cases.

Then $$$T$$$ lines, each of which contains a single integer, $$$N$$$ $$$(1 \le N \le 10^{18})$$$.

Output

For each test case output a line containing a single integer: the exclusive or of every number between $$$1$$$ and $$$N$$$.

Example
Input
3
1
2
5
Output
1
3
1

E. Aliquot Sum
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A divisor of a positive integer $$$n$$$ is an integer $$$d$$$ where $$$m=\frac{n}{d}$$$ is an integer. In this problem, we define the aliquot sum $$$s(n)$$$ of a positive integer $$$n$$$ as the sum of all divisors of $$$n$$$ other than $$$n$$$ itself. For examples, $$$s(12)=1+2+3+4+6=16$$$, $$$s(21)=1+3+7=11$$$, and $$$s(28)=1+2+4+7+14=28$$$.

With the aliquot sum, we can classify positive integers into three types: abundant numbers, deficient numbers, and perfect numbers. The rules are as follows.

  1. A positive integer $$$x$$$ is an abundant number if $$$s(x) \gt x$$$.
  2. A positive intewer $$$y$$$ is a deficient number if $$$s(y) \lt y$$$.
  3. A positive integer $$$z$$$ is a perfect number if $$$s(z)=z$$$.

You are given a list of positive integers. Please write a program to classify them.

Input

The first line of the input contains one positive integer $$$T$$$ indicating the number of test cases. The second line of the input contains $$$T$$$ space-separated positive integers $$$n_1,\dots,n_T$$$.

  • $$$1\le T\le 10^6$$$
  • $$$1 \le n_i \le 10^6$$$ for $$$i \in \{1,2,\dots,T\}$$$.
Output

Output $$$T$$$ lines. If $$$n_i$$$ is an abundant number, then print abundant on the $$$i$$$-th line. If $$$n_i$$$ is a deficient number, then print deficient on the $$$i$$$-th line. If $$$n_i$$$ is a perfect number, then print perfect on the $$$i$$$-th line.

Example
Input
3
12 21 28
Output
abundant
deficient
perfect

F. Fields Division
time limit per test
0.8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Silva family is a wheat producer in the interior of Brazil. They have a huge plantation managed by Mr. and Mrs. Silva. But the plantation has a peculiar shape: it has $$$N$$$ fields numbered from $$$1$$$ to $$$N$$$, connected by $$$M$$$ two-way roads. To facilitate the work at harvest time, the plantation was designed in such a way that there is a path between each pair of fields using the existing roads. In addition, the fields have different sizes, thus impacting the productivity of each one. The $$$i$$$-th field has a yield of $$$2^i$$$ kg of wheat per year.

As time went by, the Silva couple got tired of taking care of the plantation and decided to leave the task to their two kids: Ana and Bob. To not have any fights between the children, the couple wants to divide the $$$N$$$ fields according to the following rules:

  • Each field must belong to exactly one sibling.
  • There must be a path between each pair of fields that belong to the same sibling, using the existing roads, and visiting only that sibling's fields.
  • The sums of the yields of each sibling's fields must be as similar as possible.
If it is not possible to divide the fields so that the sums of the yields are equal, Ana will get the fields with the larger sum since she's the eldest sibling.

When the couple tried to make this division, they realized that the task would be very complex, so they asked for your help. Given the fields and the roads, your job is to help the Silva family to divide the fields between the two siblings the way they wish.

Input

The first line contains two integers $$$N$$$ ($$$2 \leq N \leq 3 \times 10^5$$$) and $$$M$$$ ($$$1 \leq M \leq 3\times 10^5$$$), indicating respectively the number of fields and the number of roads. Each of the next $$$M$$$ lines contains two integers $$$U$$$ and $$$V$$$ ($$$1 \leq U,V \leq N$$$ and $$$U \neq V$$$), denoting that there's a two-way road between fields $$$U$$$ and $$$V$$$. It is guaranteed that there is a path between each pair of fields using the given roads, and there is at most one road between each pair of fields.

Output

Output a single line with a string of length $$$N$$$ such that its $$$i$$$-th character is either the uppercase letter "A" or the uppercase letter "B", indicating respectively that Ana or Bob should receive the $$$i$$$-th field. If there are multiple solutions, output any of them.

Examples
Input
3 2
1 3
3 2
Output
ABA
Input
6 6
3 5
2 6
1 3
3 6
5 1
4 6
Output
BABABA

G. Yazan's game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yazan created a new game for us hopefully it's easy

You are given a binary grid with n rows and m columns. (each cell is $$$0$$$ or $$$1$$$), you can select one cell with value equal to $$$1$$$ and turn all its neighbors' value to $$$1$$$, you can only do this operation once (two cells are considered to be neighboring if they have a common edge or corner).

If you can turn all values to 1 print WIN otherwise print LOSE

1001
1110
1001
1111
1111
1111
1111
1111

In the above example we can select $$$cell(2,3)$$$ and turn all it's neighbors to $$$1$$$ so all values will be equal to $$$1$$$ ($$$cell(i,j)$$$ represent the cell in the i-th row and j-th column).

Input

The first line contains two positive integers n and m ($$$ 1 \le n,m \le 500$$$) the number of rows and the number of columns, respectively.

The following $$$n$$$ lines contain $$$m$$$ integers each, the $$$j$$$-th element in the $$$i$$$-th line $$$a_{i,j}$$$ is the number written in the $$$j$$$-th cell of the i-th row ($$$ 0 \le a_{i,j} \le 1 $$$).

Output

If you can turn all values to 1 print "WIN" (without quotes). Otherwise print "LOSE".

Examples
Input
4 4
1 0 0 1
1 1 1 0
1 0 0 1
1 1 1 1
Output
WIN
Input
2 5
1 0 0 0 1
1 0 0 0 1
Output
LOSE