Cataratas do Pinhão 2025
A. Analysis of a Hike
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Trojack is mapping the genetic diversity of Araucaria trees along an ecological hike that symbolically stretches from Foz do Iguaçu to Curitiba. He collected samples from $$$N$$$ trees in sequence and assigned each one a genetic identifier.

His research seeks to find sections of the trail that are genetically rich. A section is considered "viable for study" if, within it, all of the trees with a genetic marker are unique.

Your task is to help Trojack find the length of the longest continuous section of trees that is "viable for study".

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \times 10^{5}$$$), the number of trees.

The second line contains $$$N$$$ integers $$$a_1, a_2,\ldots,a_N$$$, where each $$$a_i$$$ ($$$1 \le a_i \le 10^{9}$$$) is the genetic identifier of each tree in the hike.

Output

Output a single integer, the length of the longest viable section.

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

B. Binarical Garden
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Binarical Garden is a famous tourist attraction in Curitibyte, known mainly for its greenhouse containing countless specimens of plants from Brazil and even other countries.

However, few tourists know that behind the greenhouse there is a gigantic garden of binary flowers positioned side by side. A binary flower located in the $$$i$$$-th position is so called because its number of petals is equal to the number of ones in the binary representation of $$$i$$$.

Dona Francisca is a curious tourist who is currently at position $$$L$$$ in the garden and wants to walk to position $$$R$$$ in order to find the largest number of petals on a binary flower in that part of the garden, including $$$L$$$ and $$$R$$$. Help Dona Francisca find this value.

Input

The input consists of a single line containing two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \le R \leq 10^{18}$$$), the range of the garden that Dona Francisca will walk.

Output

The output should contain only a single integer, the largest number of petals in the given range.

Examples
Input
7 15
Output
4
Input
1 1000000000
Output
29

C. Cavern of Runes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yuri Alberto, the people's favorite and Corinthians' star number 9, will be in Curitiba on August 27 to face Athletico Paranaense in the quarterfinals of the Copa do Brasil. Obviously, his victory is already a sure thing because there's no way a small team like CAP can beat the biggest team in the world!

Therefore, Yuri and his adventurous spirit have already planned to take a tour of the state of Paraná after his victory. He is truly worthy of the title of protagonist, as in addition to playing very well, he also dominates a great deal of knowledge about archaeology and rock runes. Because of this, the tour he chose to take was to enter a cave filled with enigmatic runes dating back more than 4000 years, with a legend of a cursed treasure waiting for some star of knowledge to rescue it.

Upon entering the cave, Yuri discovered that the runes are organized into $$$N$$$ panels, each containing a sequence of ancient numbers. A legend carved on the wall reveals:

To unlock the secret of the cursed treasure, the seeker must first purify each panel, maximizing the common essence of each sequence. The seeker may remove one of the runes from the sequence if desired to maximize the common essence of a sequence. Once the panels are purified, gather all the essences obtained. The destination of the treasure will be the smallest possible harmonious multiple of the gathered essences, and it is possible to remove one of the essences (if more than one exists) to minimize the harmonious multiple.

The common essence of a set is defined as the largest number that is a factor of all numbers, better known as the greatest common divisor (GCD). The harmonious multiple of a set is defined as the smallest integer that is a multiple of all elements of the set, better known as the least common multiple (LCM).

Yuri Alberto, with his expertise, knows that the solution to this puzzle requires precision and efficiency, as the runes can be numerous and the treasure will not wait. He has asked for your help in developing a program that will find the value of the cave's puzzle.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^{5}$$$), the number of panels. This is followed by $$$N$$$ lines, each representing a panel. For each panel, an integer $$$A$$$ ($$$2 \leq A \leq 10^{5}$$$) is first given, representing the number of runes on that panel, followed by $$$A$$$ positive integers $$$v_j$$$ ($$$1 \leq v_j \leq 42$$$), representing the values of the runes. The sum of all $$$A$$$ does not exceed $$$2 \times 10^{5}$$$.

Output

A single integer, the value of the cave riddle after following the ritual described. It is guaranteed that this value does not exceed $$$10^{18}$$$.

Examples
Input
3
3 12 24 30
2 8 6
3 4 6 8
Output
8
Input
4
4 32 35 42 15
2 35 40
2 24 12
3 24 11 7
Output
24
Note

Explanation for example 1

  • In the first panel $$$[12,24,30]$$$: removing $$$30$$$ results in $$$\mathrm{GCD}(12,24) = 12$$$, which is the largest possible value.
  • In the second panel $$$[8,6]$$$: removing $$$6$$$ results in $$$\mathrm{GCD}(8) = 8$$$, which is the largest possible value.
  • In the third panel $$$[4,6,8]$$$: removing $$$6$$$ results in $$$\mathrm{GCD}(4,8) = 4$$$, which is the largest possible value.

Collecting the essences: $$$[12,8,4]$$$. Removing $$$12$$$, we have $$$\mathrm{LCM}(8,4) = 8$$$, which is the smallest possible value. Therefore, the final result is $$$8$$$.

D. Dilemma of Movies
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Amós, Carlos, and Eduarda like to have movie nights at Carlos's house. On these movie nights, Carlos invites his $$$M$$$ friends (including Amós and Eduarda, since Carlos is the owner of the house). For the session, they need to choose which movies to watch from a collection of $$$N$$$ available titles. The selection can contain any number of movies, including none.

Each of the $$$N$$$ friends has two opinions about the available movies. The opinions are of the type "movie $$$i$$$ is good" or "movie $$$i$$$ is bad." Your task is to choose a set of movies to watch so that at least one of each friend's two opinions is satisfied.

An opinion is satisfied if a movie that the friend considers "good" is included in the selection, or if a movie that the friend considers "bad" is left out.

Input

The first line of input contains the integers $$$N$$$ ($$$2 \leq N \leq 10^{5}$$$) and $$$M$$$ ($$$2 \leq M \leq 10^{5}$$$), the number of friends and the number of movies, respectively.

The following $$$N$$$ lines of input contain the friends' suggestions. Each line contains two opinions, where each opinion has the form "S $$$i$$$" (movie $$$i$$$ is good) or "N $$$i$$$" (movie $$$i$$$ is bad), where $$$i$$$ is an integer with $$$1 \le i \le M$$$.

Output

Print a line with $$$M$$$ letters, for each movie "S" if it is included and "N" if it is not. If there are multiple solutions, print any one of them.

If there is no solution, print "IMPOSSIVEL".

Examples
Input
3 5
S 1 S 2
N 1 S 3
S 4 N 2
Output
N S S S N 
Input
2 6
N 3 S 6
N 6 S 3
Output
N N N N N N 
Input
4 2
N 1 S 2
N 2 S 1
N 1 N 1
S 2 S 2
Output
IMPOSSIVEL

E. Extreme Mathematics
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ebert is the best student in Linear Algebra VII in his class, so his mathematical knowledge is quite extensive. As a result, after a mind-boggling test on the subject, several students asked him how he had answered a certain question on the test. This question involved planes in a 4-dimensional space, and Ebert, with all his wisdom, explained that the intersection of two planes in $$$\mathbb{R}^4$$$ can be a single point. "It's too trivial to notice that!" exclaimed Ebert, demonstrating the planes with his own hands.

Now, several students started asking Ebert for help, but they were so annoying that he decided he didn't want to waste any more time on it. But, since he's a nice guy, he decided to ask you to write a program that would solve the problem for him, so he could just run the program. Help Ebert find the coordinates of the intersections!

Input

The first line of input consists of an integer $$$T$$$ ($$$1 \leq T \leq 10^{4}$$$), the number of test cases. Each test case has six lines, each containing four integers $$$X_i, Y_i, Z_i$$$ and $$$W_i$$$ ($$$-10000 \leq X_i, Y_i, Z_i, W_i \leq 10000$$$).

The first line of each test case represents the displacement vector $$$A = (X_1, Y_1, Z_1, W_1)$$$. The second and third lines represent the direction vectors $$$B = (X_2, Y_2, Z_2, W_2)$$$ and $$$C = (X_3, Y_3, Z_3, W_3)$$$, respectively.

The fourth line represents the displacement vector $$$D = (X_4, Y_4, Z_4, W_4)$$$. The fifth and sixth lines represent the direction vectors $$$E = (X_5, Y_5, Z_5, W_5)$$$ and $$$F = (X_6, Y_6, Z_6, W_6)$$$, respectively.

The first plane is defined by $$$A + u_1B + v_1C$$$, where $$$u_1$$$ and $$$v_1$$$ are real numbers. The second plane is defined by $$$D + u_2E + v_2F$$$, where $$$u_2$$$ and $$$v_2$$$ are real numbers.

It is guaranteed that the planes are not degenerate, i.e., the pairs $$$B$$$ and $$$C$$$ and $$$E$$$ and $$$F$$$ are linearly independent.

Output

For each test case, if there is a unique intersection between the two planes, print a line containing four real numbers representing the values $$$u_1, v_1, u_2, v_2$$$. Otherwise, print only the value $$$-1$$$.

Your answer will be considered correct if the absolute or relative error is less than $$$10^{-6}$$$. That is, if your answer is $$$a$$$ and the correct answer is $$$b$$$, then the judge will accept your answer if $$$|a - b| \leq 10^{-6} \cdot \max(1, |b|)$$$.

Examples
Input
1
0 0 0 0
1 0 0 0
0 1 0 0
0 0 0 0
0 0 1 0
0 0 0 1
Output
0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 
Input
2
4 9 2 0
0 9 4 2
2 8 1 2
8 7 4 9
1 0 0 0
5 8 2 1
5 5 5 5
1 4 2 7
3 7 6 2
4 8 3 0
7 4 14 7
2 4 4 9
Output
4.476190476190476 5.333333333333333 46.428571428571429 -10.619047619047619 
-1

F. Framed Photo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

At the end of the big Unioeste Programming Marathon, euphoria took over the room. To capture the iconic moment, all the competitors threw their badges in the air in celebration. João, the event's Social Media Wizard, captured a spectacular photo of that moment.

Now, João needs to post this photo on Instagram, but the original image is too wide, full of empty spaces that diminish the visual impact. He wants to make a rectangular cut aligned with the axes that perfectly frames all the badges. To create a visually powerful and minimalist composition, he needs this frame to be the smallest rectangle possible that still contains all the badges.

Being a perfectionist, but also... "computationally efficient" (not to say lazy), João decided to turn his task into one last challenge. He used software to identify the coordinates of the center of each badge in the photo. Now, he asks for your help, as one of the brilliant coders, to create a program that determines the exact coordinates of the four corners of the "perfect frame."

Input

The first line of input will contain an integer $$$N$$$ ($$$1 \le N \le 10^{6}$$$), the number of badges in the photo. The next $$$N$$$ lines will contain two integers each, $$$x_i$$$ $$$y_i$$$ ($$$-10000 \le x_i, y_i \le 10000$$$), the coordinates of each badge in the photo.

Output

Your program should print four lines. Each line should contain the $$$x$$$ and $$$y$$$ coordinates of one of the vertices of the smallest rectangle, separated by a space. The vertices can be printed in any order.

Examples
Input
5
4 5
-1 2
8 -3
2 9
-4 0
Output
-4 -3
8 -3
8 9
-4 9
Input
4
-3 5
10 5
0 5
10 5
Output
-3 5
10 5
10 5
-3 5

G. Great Tourist
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ana, a great tourist, decided to take advantage of the border between Foz do Iguaçu and Ciudad Del Este and go shopping in Paraguay. She has a list of $$$N$$$ products she would like to bring back. However, when crossing the Friendship Bridge, there is a risk of being stopped by the Federal Revenue Service. To minimize this risk, Ana imposes two restrictions on what she will bring with her:

  1. The sum of the prices of the products cannot exceed $$$K$$$;
  2. Some pairs of products $$$\{i, j\}$$$ have a higher risk of being stopped if they are taken together. Ana does not want to take any chances, so she will take at most one product from each of these pairs.
Input

The first line of the input contains three integers: $$$N$$$ ($$$2 \leq N \leq 20$$$), $$$M$$$ ($$$0 \leq M \leq N(N-1)/2$$$), and $$$K$$$ ($$$1 \leq K \leq 10^{18}$$$), the number of products, the number of forbidden pairs, and the maximum limit.

The second line of input contains $$$N$$$ numbers $$$a_1, a_2, ..., a_N$$$, the price of the $$$i$$$-th product ($$$1 \leq a_i \leq 10^{18}$$$).

The next $$$M$$$ lines are distinct and each contain a pair of numbers $$$i$$$ and $$$j$$$ ($$$1 \leq i \lt j \leq N)$$$, representing the indices of the products that have a higher risk of being stopped if taken together.

Output

Output the number of product subsets that Ana can choose from that meet the constraints.

Examples
Input
4 1 100
1 2 3 4
1 2
Output
12
Input
4 1 8
1 2 3 4
1 2
Output
11

H. Has a Unilestep ever existed?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Nikolas was intrigued by the name of Unioeste: State University of Western Paraná. According to his reasoning, why specify that the university is in the "West" (oeste in Portuguese) of Paraná, if there is no State University of "Eastern" (leste in Portuguese) Paraná? To correct this geographical injustice, he decided to found Unilestep (State University of Eastern Paraná).

However, the master plan for cities in the east includes some rules that must be followed:

  • The land cannot have a zero area.
  • The land must be a square with sides of integer measurements.
  • The area of the land, in square meters, must be a number that has between $$$L$$$ and $$$R$$$ digits, inclusive.

For example, for $$$L = 2$$$ and $$$R = 5$$$:

  • A square plot with an area equal to $$$64\;\text{m}^2$$$ can be used, as its area has two digits and its sides are integers.
  • A square plot of land with an area equal to $$$500\;\text{m}^2$$$ cannot be used, because although its area has the correct number of digits, the size of its sides is not an integer.
  • A square plot of land with an area equal to $$$1\;\text{m}^2$$$ cannot be used, because its area has only 1 digit, which is outside the range $$$[2, 5]$$$.

To help Nikolas choose the ideal plot of land to build Unilestep, write a program that, given the values of $$$L$$$ and $$$R$$$, reports how many distinct plots of land he can use. A plot of land is considered distinct from another only if its area is different.

Input

The first line of the input contains the integer $$$T$$$ $$$(1 \leq T \leq 10^{3})$$$, the number of test cases. This is followed by $$$T$$$ lines, each line being a test case containing two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq 17$$$).

Output

For each test case, your program should output a line containing an integer: the number of different plots of land that Nikolas can use, given the values of $$$L$$$ and $$$R$$$ provided.

Examples
Input
1
2 3
Output
28
Input
2
9 12
10 17
Output
990000
316196144

I. Itinerary of a Tourist
time limit per test
4.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Thiago is a tourist exploring the wonderful city of Curitiba, in Paraná, famous for its beauty (and cold weather). The map of the region can be represented by $$$N$$$ locations and $$$M$$$ roads connecting them. Each road has an associated travel time, in minutes.

Thiago wants to visit $$$P$$$ tourist attractions, which are the first $$$P$$$ locations on his map, such as the Botanical Garden, the Oscar Niemeyer Museum, and the huge UFPR. For each of these attractions, he has assigned a value of "happiness" that he would feel when visiting them for the first time.

Unfortunately, his time is short. He has only one day for his tour, which starts at 8:00 a.m. at his hotel (located at location $$$N$$$) and must end before midnight (12:00 a.m.). The time to visit each location depends on the tourist attraction to be visited. He can visit the tourist attractions in any order he wants and does not need to return to the hotel.

As a close friend of Thiago's and a skilled programmer, you have decided to assist him. Your task is to develop a program that determines the optimal route for Thiago, that is, the maximum sum of happiness from the locations visited without exceeding the time limit.

Input

The first line of the input contains four integers: the number of locations $$$N$$$ ($$$2 \le N \le 2 \times 10^{5}$$$), the number of roads $$$M$$$ ($$$N-1 \le M \le 2 \times 10^{5}$$$), and the number of tourist attractions $$$P$$$ ($$$1 \le P \le 20$$$). It is guaranteed that the graph is connected and that $$$P \lt N$$$.

The next $$$M$$$ lines describe the roads in the city. Each line contains three integers $$$u$$$, $$$v$$$, and $$$w$$$, where $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$) represent the locations connected by the road, and $$$w$$$ ($$$1 \le w \le 180$$$) represents the travel time in minutes. The roads are two-way, and there are no repeated roads or roads with $$$u = v$$$ in the input.

The next line contains $$$P$$$ distinct integers $$$f_1, f_2,\ldots,f_P$$$ where each $$$f_i$$$ ($$$1 \le f_i \le 10^5$$$) represents the happiness Thiago gets from visiting tourist spot $$$i$$$ for the first time.

The last line of the input contains $$$P$$$ integers $$$t_1, t_2,\ldots,t_p$$$ where $$$t_i$$$ ($$$1 \le t_i \le 120$$$) represents the time spent, in minutes, at tourist attraction $$$i$$$.

Output

Output a single integer, the maximum amount of happiness that Thiago can achieve.

Examples
Input
4 3 2
4 1 100
1 3 150
3 2 50
50 80
30 40
Output
130
Input
8 10 4
8 6 120
6 1 150
1 2 100
2 3 170
3 4 180
4 7 90
7 5 110
6 4 160
1 7 170
8 5 130
100 60 70 80
120 60 80 40
Output
250
Input
5 4 3
5 4 170
5 1 170
4 2 170
2 3 100
160 120 110
120 120 120
Output
280

J. Jocund Lecture
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Andrade, Cosenza, and Ebert are in the middle of a lecture, and they are obviously bored. To pass the time, they decide to play a game on a tree. Andrade generates a tree with $$$N$$$ nodes, with node 1 being the root, and each edge has a weight $$$w$$$. Then, Cosenza and Ebert choose two nodes $$$u$$$ and $$$v$$$ from the tree, and the game consists of calculating the sum of the weights of the edges on the path from the root to $$$u$$$ and the sum of the weights of the edges on the path from the root to $$$v$$$. The sum of the weights is calculated modulo $$$10^{5}$$$. Then, the exclusive OR (xor) between the two sums is calculated bit by bit, and the result is the value of the game for that pair of nodes.

They repeat this process several times, choosing different pairs of nodes, and want to know the different results they can obtain.

Input

The first line of the input contains an integer $$$N$$$ $$$(2 \leq N \leq 10^{5})$$$, the number of nodes in the tree. The next $$$N - 1$$$ lines contain three integers $$$u$$$, $$$v$$$, and $$$w$$$ $$$(1 \leq u, v \leq N; 0 \leq w \leq 10^{9})$$$, indicating that there is an edge between nodes $$$u$$$ and $$$v$$$ with weight $$$w$$$.

Output

The first line of the output contains an integer $$$M$$$, the number of distinct possible outcomes of the game. The second line contains $$$M$$$ distinct integers, representing the possible outcomes, in ascending order.

Examples
Input
6
1 2 4
1 3 2
2 4 3
3 6 10
3 5 94
Output
16
0 2 3 4 5 6 7 8 11 12 14 96 98 100 103 108
Input
2
1 2 998244353
Output
2
0 44353

K. K Common Interests
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pinhão is a new social network that is becoming a craze on the internet. On it, users can interact, send messages, and share posts. The great thing about Pinhão is the formation of "pinhas": automatic groups of people who share common interests. A user can only view and share posts from the pinhas they participate in. In addition to this, when a user posts or shares something, that post becomes visible in all the pinhas they are part of.

Currently, the social network has $$$N$$$ active users. Each person's interest is represented by a string of $$$L$$$ characters. Two users belong to the same pinha if their level of common interest is greater than or equal to a value $$$K$$$. This level of interest is defined as the size of the largest common substring between the strings of interest of the two users.

For example: If user A has the string of interest "acabaa" and user B has "abcccc," the largest common substring between them is "ab." Therefore, the level of common interest is 2. If $$$K\leq2$$$, they will belong to the same cluster.

The administrators of Pinhão have hired you for a study. You will receive the values of $$$L$$$ and $$$K$$$, in addition to the strings of interest of all $$$N$$$ users. Your goal is to find out how many shares, at a minimum, are necessary for a publication by user 1 to be seen by user $$$N$$$.

Input

The first line of the input contains three integers, $$$N$$$ ($$$1 \le N \le 5 \times 10^{4}$$$), the number of users on the social network, $$$L$$$, the size of the strings of interest, and $$$K$$$ ($$$1 \le K \le L \le 20$$$), the minimum level of common interest for two users to participate in the same cluster. This is followed by $$$N$$$ lines, each containing a string consisting only of lowercase letters of size $$$L$$$, where line $$$i$$$ represents the interests of the $$$i$$$-th user.

Output

The output should be a single integer: the minimum number of shares required for a post by user 1 to be visible to user $$$N$$$, or -1 if this is not possible.

Examples
Input
3 4 2
abcd
abeb
zzeb
Output
1
Input
3 4 4
zzzz
aaaa
aaaa
Output
-1
Note

Explanation for example 1

Users 1 and 2 are part of one cluster, and users 2 and 3 are part of another cluster. Thus, a post by user 1 must be shared by user 2 to be visible to user 3.

Explanation for example 2

User 1 is isolated in their own cluster, so it is impossible for them to reach user $$$N$$$.

L. Liberty from Graphs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Paulinha is training for the SBC Programming Marathon and has a clear goal: to advance to the national stage, which will be held in the Liberdade neighborhood of São Paulo. She knows that to do so, she needs to solve at least $$$K$$$ problems.

Paulinha is extremely intelligent and can solve any problem, regardless of the topic, but there is one small problem: Paulinha simply hates graph questions.

Your task is to help Paulinha figure out the minimum number of graph problems she needs to solve to reach her goal.

Input

The first line consists of integers $$$N$$$ ($$$1 \le N \le 10^5$$$), representing the total number of topics, the minimum number of problems $$$K$$$ ($$$1 \le K \le \sum_{i=1}^{N} a_i$$$) that Paulinha needs to solve to pass the stage, and an integer $$$G$$$ ($$$1 \le G \le N$$$), the index corresponding to the graph problems.

The second line contains $$$N$$$ integers, $$$a_1, a_2, \dots, a_{N}$$$, where $$$a_i$$$ ($$$1 \le a_i \le 1000$$$) represents the number of questions available for topic $$$i$$$.

Output

Output a single integer, the minimum number of graph questions that Paulinha needs to solve to pass the level.

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

M. Mirage of the Waterfalls
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An ancient legend from Foz do Iguaçu tells of a rare mirage that forms in the Devil's Throat: for a single, fleeting moment, a horizontal trail of barrels appears in the middle of the water curtain. Maria, a fearless acrobat, is determined to become the first to cross this trail before it disappears.

For the crossing, the waterfall is modeled as a line of $$$N$$$ positions for barrels, numbered from $$$0$$$ to $$$N-1$$$. Maria starts from the shore at position $$$-1$$$ and her goal is to reach the opposite shore at position $$$N$$$. Her jumping ability is $$$K$$$, which means she can jump from a foothold $$$i$$$ to a barrel $$$j$$$ if $$$(j-i) \le K$$$. Naturally, she can only land on barrels that are available in the mirage.

The biggest challenge is the chaotic nature of the waterfall, which changes the configuration of the barrels. Your task is to analyze $$$Q$$$ of these events and determine, for the initial configuration and after each change, whether Maria can cross the waterfall.

Input

The first line of the input contains three integers separated by spaces: $$$N$$$, $$$Q$$$, and $$$K$$$ ($$$1 \le N, Q \le 2 \times 10^{5}$$$, $$$1 \le K \le 10^{9}$$$), representing the number of barrels, the number of events, and Maria's jumping ability, respectively. The second line contains $$$N$$$ integers, $$$a_1, a_2, \ldots, a_{N}$$$, where $$$a_i = 1$$$ if the $$$i$$$-th barrel is initially usable, and $$$a_i = 0$$$ if it is broken.

The next $$$Q$$$ lines describe the events. Each line contains three integers $$$T$$$ ($$$1 \le T \le 2$$$), $$$L$$$ and $$$R$$$ ($$$1 \le L \le R \le N$$$).

  • If $$$T = 1$$$, the river dumps more barrels into the waterfall. In the range of positions $$$[L, R]$$$, all barrels become available.
  • If $$$T = 2$$$, a strong current sweeps the barrels away. In the range of positions $$$[L, R]$$$, all barrels become unavailable.
Output

The output should contain $$$Q+1$$$ lines, representing the answer for the initial state and all subsequent states. For each answer, print "SIM" if the traversal is possible, and "NAO" otherwise.

Examples
Input
10 3 4
1 1 0 0 0 0 0 0 1 1
1 5 6
2 5 6
1 1 10
Output
NAO
SIM
NAO
SIM
Input
8 2 3
0 0 1 0 0 1 0 0
2 6 6
1 6 7
Output
SIM
NAO
SIM

N. Name of the Marathon?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Everyone knows that the hardest part of organizing a programming marathon is choosing a name. You and your MarathonFriends are organizing a mini programming marathon and are discussing which name to choose!

After much thought, you are torn between two names: Cataratas do Pinhão and Pinhão das Cataratas. Obviously, a vote will be held to decide the winning name. Each MarathonFriend will write 1 (Cataratas do Pinhão) or 2 (Pinhão das Cataratas) on a piece of paper.

There will be many votes, so many votes that you will need many hands to count them! Unfortunately, you only have two hands =c. That is why you decide to write a program that counts all the votes and decides the winning name.

Input

The first line of input contains an integer $$$N$$$ ($$$11 \leq N \leq 10^{5}$$$), the number of votes received.

The second line of input contains $$$N$$$ numbers $$$a_1, a_2, \ldots, a_N$$$, the vote of the $$$i$$$-th MaratonAmigo.

Output

Output the winning name. In case of a tie, print "Cascatiba?"

Examples
Input
12
1 1 1 1 1 1 2 2 2 2 2 2
Output
Cascatiba?
Input
12
1 1 1 1 1 1 1 2 2 2 2 2
Output
Cataratas do Pinhao
Input
12
1 1 1 1 1 2 2 2 2 2 2 2
Output
Pinhao das Cataratas