"The best and most beautiful things in this world cannot be seen or even heard, but must be felt with the heart" - Helen Keller
4 days from now, is a special day ! It's not just a random Wednesday, but the famous Valentine's Day !
All the shops in the town are offering intersting items. The cashier does $$$n$$$ operations, summing $$$ai$$$ values, $$$1\leq i \leq n$$$, where $$$a_{i} \gt 0$$$ means that the price goes higher, or it's a discount if $$$a_{i} \leq 0$$$
As a perfectionist programmer, you only buy if the final sum is exactly $$$14$$$ Dinars, else you'll pass the offer.
The first line contains the integer $$$n$$$, the number of presents. $$$(1 \leq n \leq 19)$$$
The second line contains $$$n$$$ integers, the value added to the cash register. $$$(-10 \leq a_{i} \leq 19)$$$
Output either "YES" or "NO". The answer is case insensitive thus "Yes", "yEs", "yes" are all accepted.
23 11
YES
6-8 -4 -3 0 12 17
YES
For the 1st test case, the sum of the two numbers $$$3$$$ and $$$11$$$ is equal to $$$14$$$.
For the 2nd test case, their sum is exactly $$$14$$$.
On Valentine's Day, Bob and Alice decided to spend a fun afternoon at the arcade, indulging in a variety of games. Among them was a quirky game centered around the summation of numbers. Being the curious nerd that he is, Bob eagerly stepped up to the challenge, determined to conquer the game and claim the prize. The game consists of an array of $$$n$$$ zeros and $$$q$$$ queries that you should apply/answer correctly; each query is one of the $$$2$$$ types:
- $$$1$$$ $$$l$$$ $$$r$$$ : write the sum of elements from $$$l$$$ to $$$r$$$ in the array
- $$$2$$$ $$$l$$$ $$$r$$$ $$$p$$$ $$$k$$$ $$$v$$$ : Add $$$v$$$ to every index $$$i$$$ such that $$$l\leq i \leq r$$$ and $$$i \% p=k$$$ (the remainder of division of $$$i$$$ by $$$p$$$ is equal to $$$k$$$)
The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ $$$(1 \leq n,q \leq 2.10^{5})$$$.
The next $$$q$$$ lines each contain one query of $$$2$$$ types:
- $$$1$$$ $$$l$$$ $$$r$$$ $$$(1\leq l \leq r \leq n)$$$
- $$$2$$$ $$$l$$$ $$$r$$$ $$$p$$$ $$$k$$$ $$$v$$$ $$$(1 \leq l \leq r \leq n, 1 \leq v \leq 10^{5}, 1 \leq p \leq 5, 0 \leq k \lt p)$$$
It is guaranteed that there is at least a query of type $$$1$$$ in the input.
Print the answers for the queries of the first type.
5 72 1 5 2 1 52 1 3 1 0 21 1 11 2 21 3 31 4 41 5 5
7 2 7 0 5
On Valentines Day, Alice and Bob went to a museum . The museum structure is a tree like structure where there are $$$n$$$ rooms connected by $$$n-1$$$ bidirectional doors, and you can go from any room to any other room. The entrance of the museum is room number 1.
Since Alice and Bob are quite different people, they may split in some room and each one of them goes into a separate route which doesn't contain the room they came from (parent room in the tree like structure). So Bob was worried if the distance would be very large between them (distance between rooms is the number of doors between them). So he asked you $$$q$$$ questions of the form:
- He gives 2 integers $$$u$$$ and $$$k$$$, you need to find the number of unordered pairs of rooms that they can end up at if they are currently at room $$$u$$$ and decided to split the path and the distance between their final rooms is greater than or equal to $$$k$$$.
Note: Splitting the route also counts the case when someone stays at the current room and the other goes into another room.
The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ $$$(2\leq n \leq 2.10^{5}, 1\leq q \leq 5*n)$$$.
The next $$$n-1$$$ lines each contain $$$2$$$ integers $$$u$$$ and $$$v$$$ $$$(1\leq u,v \leq n)$$$, which means there is a door between room $$$u$$$ and room $$$v$$$, it's guaranteed that you can go from any room to any other room.
The next $$$q$$$ lines each contain $$$2$$$ integers $$$u$$$ and $$$k$$$ $$$(1\leq u \leq n, 1\leq k \leq n-1)$$$
It is guaranteed that every number $$$u$$$ doesn't appear more than $$$5$$$ times in the queries.
For the answer for each question in separate lines.
9 41 22 33 44 52 62 76 84 91 22 33 26 1
7 13 2 1
Explanation of the third query: the only 2 possible pairs are $$$(3,5)$$$ $$$(3,9)$$$, the pair $$$(5,9)$$$ doesn't count since they splitted their route at room $$$4$$$ and not $$$3$$$
As a respectful and punctual boyfriend, you have to be on time for your dinner reservation. However, you are also a good citizen and respect traffic lights, or else you'll get a fine and you'll have no money left for food :(
In an $$$[Ox)$$$ plan with the restaurant $$$X$$$ meters away and you being at position $$$0$$$, you encounter $$$n$$$ traffic lights denoted by the triplets $$$c$$$ $$$p$$$ $$$t$$$:
- $$$c$$$: character, indicating the signal color, either 'R' (red) or 'G' (green).
- $$$p$$$: integer, position of the traffic light along the road.
- $$$t$$$: integer, time duration for each state switch.
Assuming you walk at a speed of $$$1$$$ $$$meter/second$$$, determine the time it takes in seconds to reach the restaurant.
The first line contains two integer $$$n$$$ and $$$X$$$, the number of traffic lights, and the distance in meters of the restaurant. $$$(1\leq n \lt X\leq 10^{5})$$$
The next $$$n$$$ lines each have $$$c$$$ $$$p$$$ $$$t$$$ $$$(1 \leq p \lt X, 1 \leq t \lt 100, c=\text{'G'}$$$ or $$$c=\text{'R'})$$$
Print the time in seconds to reach the restaurant, while respecting all the traffic lights.
3 100R 5 10R 10 50G 50 70
190
Note 1 : If $$$c$$$ is 'R' and $$$t$$$ is 5, it implies that from $$$[0,5[$$$ seconds, the signal is red; from $$$[5,10[$$$, it's green; $$$[10,15[$$$, red, and so on...
Note 2: All of the traffic lights' positions are distinct.
In Dinoland, it is a custom to buy your loved one an extravagant gift for Valentine's day!
To honour the tradition, Danny is gathering money to surprise his girlfriend Dannita. However, the gift that he wants to buy is so expensive, that his current savings won't be enough. Luckily, he heard that the local flower shop is recruiting interns to help with the management of the clients' orders.
Whenever a client orders a custom bouquet, Danny needs to create a new file that will contain all the data concerning that bouquet. And whenever a client's bouquet is ready he needs to delete the file containing that bouquet's information. And sometimes his manager will ask him about the number of the bouquets that they still need to prepare.
Danny also recently learned how to use the Command Line, so he will use the following commands to do his tasks as an intern:
- touch FILENAME: this command is used to create a new file with a certain file name. If a file with the given name already exists, a new file won't be created.
- rm FILENAME: this command is used to delete a new file with a certain file name. If no file with that name exists, nothing happens.
However, Danny still doesn't know how to count the number of files remaining using Command Line. So he asks for your help.
You will access to the list of commands he typed, and whenever he types the command ask, you need to provide him with the number of available files. Can you help him?
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$). Each of the next $$$N$$$ lines contains one of the three possible commands (touch, rm or ask). It is guaranteed that there will be at least one command of type ask.
The sum of lengths of the files in the input doesn't exceed $$$2.10^6$$$.
For each command of type ask, you need to output one integer: the number of files currently available.
7 touch love_is_in_the_air ask touch Valentine rm love_is_in_the_air ask rm Danny is cool ask
1 1 1
Bob and Alice live in a country that can be represented as a $$$2D$$$ grid of $$$n$$$ rows and $$$m$$$ columns where rows are numbered from top to bottom and columns are numbered from left to right. Bob lives at coordinates $$$(1,1)$$$ and Alice lives at coordinates $$$(n,m)$$$.
On Valentines Day, Bob wants to visit his girlfriend Alice and he would like to paint a picture to give to her. The picture needs $$$C$$$ different colors. Bob currently doesn't have any color so he would like to purchase colors and paint the picture on the way to his girlfriend to gain some time.
There are some shops in the country where each shop sells only one color and has an unlimited amount of units of that color.
The price of the paints of colors doesn't matter for Bob so he can spend any amount of money, but the time is crucial. So he would like to know what is the minimum time to go from his home to Alice's home with the picture ready.
Since Bob is smart, he can mix $$$2$$$ colors to get another color, but this operation will take time and depends on the color. So there are $$$K$$$ possible mixtures defined as follows: $$$(c_{1},c_{2},c_{3},t)$$$, which means mixing $$$c_{1}$$$ with $$$c_{2}$$$ will produce $$$c_{3}$$$ and takes $$$t$$$ time.
Bob can move from $$$(a,b)$$$ to $$$(c,d)$$$ if and only if $$$1\leq c\leq n$$$ and $$$1\leq d\leq m$$$ and $$$|a-c|+|b-d|=1$$$ and it takes $$$1$$$ unit of time.
Note that : drawing time and buying time are negligible
The first line contains $$$4$$$ integers $$$n$$$, $$$m$$$ $$$(1\leq n,m \leq 100)$$$, $$$C$$$ $$$(1\leq C \leq 7)$$$ and $$$K$$$ $$$(0\leq K \leq \frac{C*(C-1)}{2})$$$.
The next $$$n$$$ lines each contain a string of length $$$m$$$ containing only digits. If $$$s_{i,j} = 0$$$ then the cell is empty otherwise it represents the color that the shop sells at coordinates $$$(i,j)$$$.
The next $$$K$$$ lines each contains $$$4$$$ integers $$$c_{1}, c_{2}, c_{3}, t$$$ the description of the mixture $$$(1\leq c_{1}, c_{2}, c_{3} \leq C,c_{1}\ne c_{2},c_{1}\ne c_{3},c_{2}\ne c_{3})$$$, $$$(1\leq t \leq 10^{5})$$$. It is guaranteed that each unordered pair $$$(c_{1},c_{2})$$$ can appear at most one time.
If it is possible to prepare the picture, print the minimum time required for Bob reach Alice's home with his picture ready. Otherwise print -1.
5 5 3 100012000000000000000300001 2 3 2
10
5 5 3 100012000000000000000300001 2 3 10
16
Valentine's Day is the perfect occasion to confess your love, and what's better than anonymous phone calls ?
You have in your phone a contact list of $$$n$$$ phone numbers, saved as name and its respective phone number.
You receive $$$q$$$ phone calls but here's the catch: You can't see the whole phone number, but rather only $$$k$$$ digits, $$$(1 \leq k\leq 8)$$$ and not necessarily in the same order. Also, among the next $$$q_{i}$$$ digits, $$$(0 \leq q_{i} \leq 9)$$$, there could be duplicates.
Tell for each query $$$q$$$ whether no phone number in your repertory matches it, many possible numbers match it, or the name of the UNIQUE person whose number matches those criteria.
In the first line, you are given an integer $$$n$$$ , $$$(1\leq n \leq 10^{4})$$$.
In the next $$$n$$$ lines, you are given a string $$$name$$$ of lowercase and uppercase english letters $$$(1\leq len(name) \leq 10)$$$ , and an-8-digits string $$$phone$$$. It's guaranteed that all the names are different and all the phones are different.
In the next line, you are given $$$q$$$ queries, $$$(1\leq q \leq 10^{6})$$$
For each $$$q$$$ lines, you get an integer $$$k$$$ , $$$(1\leq k \leq 8)$$$, the number of known digits, and a string $$$partial phone$$$ of size $$$k$$$.
After each query, output "NONE" if no phone number in your repertory matches it, "MANY" if many possible persons match it, or the $$$name$$$ of the UNIQUE person that matches it.
3Mahdi 12345678Elyes 11223344Mohamed 0088121251 52 113 1117 76543211 9
Mahdi MANY NONE Mahdi NONE
After a sore defeat at the "Gift Battle", Danny decided to give up on buying a fancy gift.
Instead, he went to the most famous Chocolate Shop of Dinoland to buy Dannita some chocolate. There, he noticed that some chocolates had some letters written on them.
The shop offers $$$N$$$ types of chocolate. These types are numbered from $$$1$$$ to $$$N$$$. Each type $$$i$$$ has a string $$$S_i$$$ written on it. Danny wonders if there are $$$4$$$ distinct types of chocolate $$$i_1$$$, $$$i_2$$$, $$$i_3$$$ and $$$i_4$$$ such that $$$S_{i_1} + S_{i_2} = S_{i_3} + S_{i_4}$$$. He wants to surprise Dannita with such types of chocolate. Help him find such types of chocolate or tell him that it is impossible.
The first line of input contains a single integer $$$N$$$ ($$$4 \leq N \leq 1000$$$).
The next $$$N$$$ lines contain the strings written on the types of chocolate. The $$$i+1^{\text{th}}$$$ line of the input contains $$$S_i$$$, the string written on the $$$i^{\text{th}}$$$ type of chocolate.
The sum of the length of all the strings will not exceed $$$10^6$$$.
Note that the strings will only consist of lowercase and uppercase English letters.
If it is impossible to find an answer, print "NO".
Otherwise, print "YES" on a line followed on the next line by $$$4$$$ integers that satisfy the condition specified in the statement. If there are multiple answers, print any of them.
6 Da nnyy Val entine Valen tine
YES 3 4 5 6
You're still in class, zoned out, thinking about your Valentine's plan, 4 days from now. You draw many dots in your notebook and wondered: How many unordered quadruples $$$i$$$,$$$j$$$,$$$k$$$ and $$$l$$$ exist such that they form a line together.
Given $$$n$$$ points $$$P_{i}$$$ with coordinates $$$x$$$ and $$$y$$$, how many 4 points $$$P_{i}$$$, $$$P_{j}$$$, $$$P_{k}$$$ and $$$P_{l}$$$ $$$(1\leq i \lt j \lt k \lt l \leq n)$$$ are collinear ?
In the first line, you're given an integer $$$n$$$, $$$(1\leq n \leq 400)$$$, the number of points you drew.
In the next $$$n$$$ lines, you're given two integers $$$x$$$ and $$$y$$$ , the x-coordinate and the y-coordinate of the $$$ith$$$ point, $$$(-10^{9}\leq x_{i},y_{i} \leq 10^{9})$$$, All points are distincts!!
Print the number of possible quadruples.
51 12 23 34 45 5
5
41 13 2-9 -94 3
0
As a caring boyfriend, it's nice to give your girlfriend flowers along with gifts. So, you decide to get the prettiest bouquet of flowers within your budget, with the highest beauty score. The dream situation is to buy all the flowers in the shop: all $$$100$$$ available flowers from each type.
The person selling flowers is friendly, so he allowed you to buy any flower with $$$1$$$ dinar no matter its type.
The bouquet beauty score, $$$Beauty$$$, is a real number $$$(0\leq Beauty \leq 100)$$$ , showing how pretty the bouquet is out of $$$100$$$. The $$$Beauty$$$ of a bouquet is defined as the sum of the beauties of the flowers in that bouquet, divided by the sum of the beauties of each possible type of flowers.
So you decided to get the bouquet with the maximum possible beauty.
In the first line, you are given the number of test cases $$$t$$$ $$$(1\leq t \leq 10)$$$.
For each test case, you're given in the first line two integers: $$$n$$$ and $$$c$$$, the number of types of flowers, your budget in dinars respectively. $$$(1\leq n \leq 5.10^{4})$$$ $$$(1\leq c \leq 10^{9})$$$.
In the second line, you get an array $$$a$$$ with $$$n$$$ real numbers, where $$$a_{i}$$$ ($$$1 \leq i \leq n$$$) representing the beauty coefficient for the $$$ith$$$ type of flower. $$$(1\leq a_{i} \leq 100)$$$.
For each testcase, output the maximum possible beauty in separate lines. The answer should have a relative error less than $$$10^{-6}$$$.
13 3704 3 2
100.000000000000000
11 309
30.000000000000000
13 1402 3 2
54.285714285714285
NB: You can't buy more than 100 flowers from the same type, as it is the number of available flowers from each type in each testcase.
Valentine's Day has come, and Bob prepared the perfect gift for his girlfriend, Alice. The gift is a rooted tree of chocolates where each chocolate has a type. To make the day more interesting, he decided to play a game with his girlfriend using the gift. The game lasts for $$$q$$$ operations, where the operation is one of the following:
- $$$1$$$ $$$u$$$ $$$v$$$ $$$k$$$ : Alice has to tell Bob how many chocolates of type $$$k$$$ exist on the simple path from $$$u$$$ to $$$v$$$.
- 2 $$$u$$$ $$$k$$$ : Bob gives the chocolate in node $$$u$$$ to Alice to eat and replaces it with chocolate of type $$$k$$$.
You have to help Alice answer the first type of operations.
The root of the tree is node $$$1$$$.
Tree: A connected acyclic undirected graph where there is only $$$1$$$ simple path between any $$$2$$$ pairs of nodes.
The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ $$$(1\leq n,q \leq 2.10^{5})$$$
The second line contains $$$n$$$ integers $$$t_{i}$$$ $$$(1\leq t_{i} \leq 10^{6})$$$, the type of the chocolate in node $$$i$$$.
The next $$$n-1$$$ lines each contain $$$2$$$ integers $$$u$$$ and $$$v$$$ $$$(1\leq u,v \leq n)$$$, which means there is an edge between node $$$u$$$ and node $$$v$$$.
The next $$$q$$$ lines contain one of $$$2$$$ operations:
- $$$1$$$ $$$u$$$ $$$v$$$ $$$k$$$ $$$(1 \leq u,v\leq n, 1\leq k \leq 10^{6})$$$
- $$$2$$$ $$$u$$$ $$$k$$$ $$$(1 \leq u\leq n, 1\leq k \leq 10^{6})$$$
Print the answer for the operations of type 1 in separate lines.
9 91 2 3 4 5 6 7 8 91 22 33 44 52 62 76 84 91 5 9 21 5 9 41 5 9 51 5 9 61 5 7 61 5 7 31 5 7 82 3 61 5 7 6
0 1 1 0 0 1 0 1
Bob, being a novice in the realm of dating, took the initiative to educate himself by purchasing a book on relationship dynamics and crucial elements within them. However, to his surprise, he mistakenly acquired a book on entity relationship diagrams, which captivated his interest nonetheless. Despite this detour, Bob remains determined to grasp the fundamentals of nurturing a healthy relationship with his girlfriend. Resorting to a tried-and-true method, he has chosen to express his affection through the timeless practice of gift-giving. As such, he has devised a schedule for presenting his girlfriend with thoughtful gifts which goes as follows:
- He can give the first gift any day of the year.
- He will always need to give another gift after at most $$$K$$$ days from the day of the last gift.
- He can breakup at any moment, so he doesn't have to give gifts anymore.
Today is day 1 of the year, and the year contains $$$L$$$ days. Help Bob count the number of distinct ways he can give gifts to his girlfriend during this year.
Notes :
- Once Bob and his girlfriend parted ways, there was no chance of reconciliation.
- Since Bob is a good person, he will give at least one gift to his girlfriend before breaking up.
The input contains 2 integers $$$L$$$ $$$(1 \leq L \leq 10^{18})$$$ and $$$K$$$ $$$(1 \leq K \leq 100)$$$.
Print one integer, the answer to the problem modulo $$$998244353$$$.
4 2
14
100 50
297200453
Valentine's day is coming soon!! It is a special day not only for humans, but also for the dinosaurs living in Dinoland!
Danny, being a popular dinosaur, got asked out by many other Dinosaurs. Indeed, he received $$$K$$$ date invitations numbered from $$$1$$$ to $$$K$$$. The $$$i^{\text{th}}$$$ date invitation was sent to him by Dinosaur $$$i$$$.
However, there is a little problem. Danny has a group of $$$N$$$ friends, that can be modelled as a tree where each node represents one of Danny's friends. Two dinosaurs are called direct friends if there is an edge between them. Two dinosaurs are friends if there is a path between them, and we say that they belong to the same friend group. Each of Danny's friends is numbered from $$$1$$$ to $$$N$$$, and the $$$i^{\text{th}}$$$ of them has a value $$$a_i$$$ that represents their dating history.
If Danny accepts the $$$i^{\text{th}}$$$ date invitation for Saint Valentine, all of his friends who have dated the dinosaur who sent that invitation will get mad and leave the friend group. A friend $$$j$$$ will get mad when Danny accepts the $$$i^{\text{th}}$$$ date invitation if and only if $$$i$$$ divides $$$a_j$$$. When a dinosaur leaves the friend group, he will not be part of the group anymore and his ties with his direct friends will disappear. As a result, the group will be fragmented, and turn into multiple smaller friend groups.
Danny is weighing the pros and cons of accepting the invitations he got. He asked for your help. He wants you to tell him, for each invitation $$$i$$$ that he got, how many friend groups he will end up with.
On the first line of input you are given two integers $$$N$$$ and $$$K$$$ $$$(1 \leq N, K \leq 10^6)$$$
On the second line of input, you are given $$$N$$$ integers $$$a_1a_2 ...a_N$$$ $$$( 1 \leq a_i \leq 10^6)$$$
On each of the next $$$N-1$$$ lines of input, you will be given two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v\leq N$$$) denoting that friends $$$u$$$ and $$$v$$$ are direct friends and that there is an edge between them. It is guaranteed that the friends form a tree.
Print $$$K$$$ integers, the number of remaining friend groups if Danny excepts each invitation.
5 3 1 3 4 6 7 1 2 1 3 3 4 4 5
0 2 1
The friends' tree looks initially like this:
- Accepting invitation $$$1$$$ will lead to Danny losing all his friends, and as a result, the number of friend groups remaining will be $$$0$$$
- Accepting invitation $$$2$$$ will lead to Danny losing friends $$$3$$$ and $$$4$$$ which leads to two separate remaining friend groups.
- Accepting invitation $$$3$$$ will lead to Danny losing friends $$$2$$$ and $$$4$$$ which leads to one remaining friend group.
Danny always suffers because of his terrible memory. Last time, he forgot the anniversary of his couple, and Dannita got extremely mad at him. Needless to say, he spent a terrible week after that.
This time, Dannita gave him an array $$$A$$$ as a present for Saint Valentine. Unfortunately, Danny lost it, and he can't remember its elements. He is in big trouble if he doesn't get it back!!
Luckily, Danny remembers a few facts about the array.
First of all, he remembers that it is a permutation of the numbers from $$$0$$$ to $$$N-1$$$. That means that it contains every number from $$$0$$$ to $$$N-1$$$ exactly once.
Secondly, he remembers that the array has the following property. Let $$$B$$$ be the array constructed as follows: $$$b_i = a_i \text{ xor } 1$$$ for each $$$1 \leq i \leq N$$$, where xor refers to the bitwise xor operation. Let $$$inv(A)$$$ be the number of inversions of the array $$$A$$$ and $$$inv(B)$$$ be the number of inversions of the array $$$B$$$ (the number of inversions is the number of pairs $$$(i,j)$$$ such that $$$i \lt j$$$ and $$$a_i \gt a_j$$$ ). Danny remembers the difference between $$$inv(B)$$$ and $$$inv(A)$$$. In other words, Danny remembers an integer $$$D$$$ where $$$D = inv(B) - inv(A)$$$.
Thirdly, Danny remembers that for all $$$0 \leq x \leq N-1$$$, $$$x$$$ and $$$x \text{ xor } 1$$$ are NOT adjacent in the array A.
Can you help Danny find the number of possible arrays A that satisfy all these conditions
The first and only line of input contains two integers $$$N$$$ and $$$D$$$ ($$$1 \leq N \leq 10^5, 0 \leq |D| \leq 10^{18}$$$)
A single integer: the number of arrays that satisfy the conditions.
Since it can be very large, print the answer modulo $$$998244353$$$.
4 0
4
The four possible arrays are $$$[0, 3, 1, 2], [1, 2, 0, 3], [2, 1, 3, 0], \text{ and } [3, 0, 2, 1]$$$
Danny has finally saved enough money to buy his girlfriend Dannita a gift!
He went to the gift shop to buy the gift that he worked so hard to buy. However once there, he found that someone else was interested in buying the same gift, and there was only one article left.
Fortunately, the gift shop's policy already states what to do in such situations. When two clients want to buy the same article, they need to play a game called "Gift Battle" to decide who will get to home with the gift.
The game goes as follows: The players are given an array of $$$N$$$ numbers. The players take turns and do the following move: During his move, each player chooses a number from the array, greater than all of the numbers that he chose before, and removes it.
The first player who finds himself unable to make a move loses.
Danny will start the game. He is wondering, if he and his opponent both play optimally, can he still win the game?
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 1000000$$$) The following line contains $$$N$$$ integers $$$a_1a_2 ... a_n$$$ ($$$1\leq a_i \leq 10^9$$$), the array of numbers given to the players
Output "WIN" if Danny wins and "LOSS" if Danny loses.
3 1 2 3
WIN