Maxwell, a great enthusiast of all forms of racing, decided to organize the UnBalloon World Kart Championship! In this championship, the best drivers from the group were chosen, each representing the initial of their name, meaning that $$$26$$$ competitors were selected, one for each letter of the alphabet. These competitors will have to compete for $$$n$$$ exciting laps, vying for the legendary title of felipe_massa.
The great journalist and photographer Isa decided to write an article about this event. However, caught up in all the competition and excitement of the race, she only managed to record the winners of $$$m$$$ consecutive laps! Isa cannot remember when she started making these notes, but she is sure that they are correct and occurred at some point during the race, and that each letter represents which driver won that lap. To finish her article, she needs to know how many ways the race as a whole could have occurred following her notes, knowing that a race is characterized only by the winners of each lap.
Thus, it is up to you, an aspiring titleholder of felipe_massa and a racing enthusiast, to answer this question. Since the number of distinct races can be very large, Isa asked that this calculation be performed modulo $$$998244353$$$. Two races are considered different if, in some lap $$$i$$$, the winner of that lap $$$i$$$ is different between the races.
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^{18}$$$, $$$1 \leq m \leq 100$$$, $$$m \leq n$$$), the total number of laps and the size of Isa's notes.
The second line contains a string $$$s$$$, the race notes, composed of $$$m$$$ lowercase characters from the Latin alphabet.
Print the number of races that could have occurred according to Isa's notes, modulo $$$998244353$$$.
6 5ilprw
52
8 5ababa
70252
100000000 15novofelipemassa
966021064
In the first test case, Isa wrote down the results of $$$5$$$ laps, with the winners of each lap being "ilprw". Since the race had a total of $$$6$$$ laps, the races "$$$X$$$ilprw" or "ilprw$$$X$$$" could have occurred, where $$$X$$$ represents any of the $$$26$$$ competitors.
In Bauru, the numbering of buildings is quite unique. Instead of the address being just Street $$$r$$$ Number $$$Y$$$, it is in the form: Street $$$r$$$ Block $$$Y$$$ Number $$$Z$$$. To simplify writing, the address is usually shortened to: Street $$$r$$$, Number $$$Y-Z$$$, that is, combining the block number with the building number. For example: Darcy Ribeiro Street, $$$9-75$$$ (block $$$9$$$, number $$$75$$$).
Dhara lives in Bauru, and one of her friends sent her a message asking her to send a package to Quintino Street, $$$A-B$$$ (block $$$A$$$, number $$$B$$$). However, instead of separating $$$A-B$$$, the message presented the two numbers together, in the form $$$AB$$$!
Help Dhara to separate the message $$$AB$$$ into $$$A$$$ and $$$B$$$, so that she can send the package. To do this, consider that $$$A$$$ and $$$B$$$ are numbers between $$$1$$$ and $$$99$$$ and that they were not written with leading zeros (for example: if $$$A = 1$$$, it cannot have been written as $$$01$$$ or $$$0001$$$, only $$$1$$$).
The input contains only one line, with the message $$$AB$$$. $$$AB$$$ is a numeric string that has between $$$2$$$ to $$$4$$$ digits.
It is guaranteed that $$$AB$$$ can be formed from valid numbers $$$A$$$ and $$$B$$$, according to the statement.
If it is possible to uniquely separate $$$AB$$$ into $$$A$$$ and $$$B$$$, print $$$A$$$ and $$$B$$$ separated by a space, on a single line.
Otherwise, that is, if there are multiple valid $$$A$$$ and $$$B$$$ that can form $$$AB$$$, print $$$-1$$$.
975
-1
11
1 1
1010
10 10
120
1 20
Adrielly really likes music, and to make her bus rides to and from UnB less boring, she decided to create her own playlist!
To do this, she selected the $$$N$$$ most recent songs she listened to (numbered from $$$1$$$ to $$$N$$$) and assigned a value $$$A_i$$$ to each song $$$i$$$. This value represents how much Adrielly likes that song — if it is negative, it is a song she regrets listening to...
Obviously, Adrielly would like to create a playlist that maximizes the sum of the values of the chosen songs! However, she currently has a song stuck in her head with the chorus: "One Every $$$K$$$! One Every $$$K$$$!...". Therefore, if she chooses song $$$i$$$ to be included in the playlist, she cannot choose any song $$$j$$$ with $$$i \lt j \lt i+K$$$.
Help Adrielly make her trips more enjoyable by determining the maximum possible sum of the values of a playlist, following the "One Every $$$K$$$" restriction!
The first line of input contains two numbers: $$$N$$$ and $$$K$$$ $$$(1 \leq K \leq N \leq 10^5)$$$. It is guaranteed that $$$K \cdot N \leq 10^5$$$.
The second line of input contains the $$$N$$$ values $$$A_i$$$ $$$(-10^9 \leq A_i \leq 10^9)$$$.
Print a single line containing the maximum possible sum of the values of a playlist, following the given restriction.
12 31 4 -5 6 19 20 -1 4 5 -3 0 10
39
3 11 2 3
6
3 1-1 -2 -3
0
4 42 3 0 2
3
In the first example case, the best option for Adrielly is to choose the songs with the values: $$$4$$$, $$$20$$$, $$$5$$$, and $$$10$$$.
In the second example case, Adrielly achieves the maximum sum by choosing all the songs.
In the third example case, it is better for Adrielly not to choose any songs because all of them are bad... So the best sum is achieved with an empty playlist (sum $$$0$$$).
In the fourth example case, Adrielly should choose the song with the value $$$3$$$.
Arthur is a spy from the renowned secret agency MI-9548. In his missions, for security reasons, he uses the most sophisticated encryption algorithm to communicate with headquarters: the Shift Cipher.
The messages sent by Arthur are represented by lists containing integer values between $$$0$$$ and $$$9999$$$. The Shift Cipher consists of choosing a "shift" between $$$0$$$ and $$$9999$$$ and adding that same value to all elements of the list. If this application causes the value of an element to exceed $$$9999$$$, the remainder of the value when divided by $$$10000$$$ should be taken.
For example, if Arthur's message is $$$[1, 2, 3, 4]$$$ and we choose the shift $$$3$$$, we will have the new list $$$[4, 5, 6, 7]$$$. If we choose the shift $$$9998$$$, we will have the list $$$[9999, 0, 1, 2]$$$.
Arthur has a favorite phrase $$$B$$$, represented by a list of numbers, and he would like to choose the encryption shift in such a way that this phrase appears as many times as possible in the encrypted message.
For example, if the message to be encrypted is $$$[1, 2, 3, 1, 2]$$$ and Arthur likes the phrase $$$[6, 7]$$$, he should choose the shift $$$5$$$, as this will result in the message $$$[6, 7, 8, 6, 7]$$$, which contains Arthur's phrase twice.
Help Arthur by finding the shift that results in the highest number of occurrences of his favorite phrase in the message $$$A$$$ to be encrypted, and additionally report the number of occurrences. If more than one shift maximizes the number of occurrences, find the smallest one.
The first line of input contains two integers $$$N$$$ and $$$M$$$ $$$(2 \le M \le N \le 10^6)$$$, which correspond to the length of the message $$$A$$$ and the length of the phrase $$$B$$$, respectively.
The second line contains $$$N$$$ integers separated by spaces: the message $$$A$$$ $$$(0 \le A_i \lt 10^4)$$$.
The third line contains $$$M$$$ integers separated by spaces: the phrase $$$B$$$ $$$(0 \le B_i \lt 10^4)$$$.
The output should contain two numbers separated by a space: a value between $$$0$$$ and $$$9999$$$, representing the smallest shift that maximizes the occurrences of the phrase, and the number of occurrences.
5 21 2 3 1 26 7
5 2
4 21 2 3 40 0
0 0
2 2452 4530 1
9548 1
Determined to improve her skills, Nikolle climbed the highest mountain known to humanity, going beyond the clouds. There, she found a monastery, where the great master Z lived. Training with him, Nikolle acquired powerful knowledge about competitive programming, such as Segment Tree Beats, Sweepline Mo, and 3D Hull Online.
After months of improvement, Nikolle returned to UnB and decided to share her knowledge with her peers. However, before delving into overly complex topics, she decided to propose a simpler challenge: to implement the weakest data structure she knows, the Serpistent Teg.
A Serpistent Teg maintains a list of stacks, initially with no stacks. The structure supports the following operations:
Show Nikolle that you have what it takes to learn her techniques!
The first line of the input contains an integer $$$Q$$$: the number of operations to be performed $$$(1 \leq Q \leq 100)$$$.
Each of the next $$$Q$$$ lines describes an operation to be performed, and the operations must be executed in the order they are given in the input. These lines start with an integer $$$t$$$, indicating the type of operation according to the statement $$$(1 \leq t \leq 3)$$$.
For every operation of type $$$3$$$, print the $$$j$$$-th number added to stack $$$i$$$. Print only one number per line, in the order they appear in the input.
1312 1 33 1 112 1 42 2 53 2 13 1 212 3 12 3 23 3 23 1 1
3 5 4 2 3
Falatro is a card game that has recently become very popular.
It is played with a nearly standard deck of cards, and the objective is to form a sequence of cards with the highest possible score, following some rules similar to poker. The difference in Falatro is that, in addition to the cards you have, you can buy jokers that can be used as modifiers to increase the score of your hand, depending on your hand.
Curious about the development of the game, John decided to include his own joker in the list of cards, the fidojoker. The rules for this joker are as follows: "All the cards in your hand will have paired trust relationships between them, and the score of your hand will be calculated as the sum, for each card, of the size of the smallest trust cycle that contains that card multiplied by its index." A trust relationship is formed by a pair of cards (A, B), where A trusts B and B trusts A. If a card does not participate in any trust cycle, it is considered to have size $$$1$$$.
Since John has difficulty thinking before playing, and he is not very good at math, he asked for your help to determine the score of his hand using the fidojoker.
The input consists of a single test case. The first line of the input contains two integers $$$N$$$ $$$(3 \leq N \leq 100)$$$ and $$$M$$$ $$$(2 \leq M \leq \frac{N \cdot (N-1)}{2})$$$, representing the number of cards in John's hand and the number of trust relationships between the cards, respectively. The next $$$M$$$ lines contain two integers $$$A$$$ and $$$B$$$ $$$(1 \leq A, B \leq N,\ A \neq B)$$$, indicating that cards $$$A$$$ and $$$B$$$ have a trust relationship between them. It is guaranteed that there are no multiple relationships between the same pair of cards.
The output should contain a single integer, representing the total score of John's hand.
4 41 22 31 34 1
22
6 62 44 64 16 35 13 1
63
In the first test case, the smallest cycle formed by the cards consists of $$$1$$$, $$$2$$$, and $$$3$$$. Additionally, card $$$4$$$ is not in any cycle. Thus, John's score is $$$1 \cdot 3 + 2 \cdot 3 + 3 \cdot 3 + 4 \cdot 1 = 22$$$.
Lucas is the owner of a new franchise of Heladitos from Goiás, specialized in producing gelatos with typical fruits from the Cerrado. Soon, a national competition will take place to elect the best gelato in Brazil, and Lucas intends to participate by launching a striking flavor: Pequi Gelato.
To evaluate the quality of a gelato, Lucas uses a formula defined as the product of the smallest score of the chosen subset of ingredients and the size of that subset. Formally, let $$$I$$$ be the set of available ingredients and $$$E$$$ the subset of ingredients chosen for gelato $$$g$$$ ($$$E \subseteq I$$$), its quality $$$Q_g$$$ is given by:
Lucas organized a list $$$a$$$ with $$$N$$$ values, corresponding to the score of each available ingredient. Additionally, to prevent the odor of the gelato from becoming unbearable, he defined a derangement $$$P$$$, where the $$$i$$$-th ingredient cannot be used together with the $$$P_i$$$-th ingredient.
Due to high demand in his store, Lucas does not have time to make this choice himself. Thus, he asks for your help to determine, based on the list of ingredients and the permutation $$$P$$$, what is the highest possible quality value that can be obtained.
The first line contains an integer $$$N$$$ $$$(2 \leq N \leq 10^5)$$$, representing the number of available ingredients.
The second line contains $$$N$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$, where each $$$a_i$$$ indicates the score of the $$$i$$$-th available ingredient.
The third line contains $$$N$$$ integers $$$P_i$$$ $$$(1 \leq P_i \leq N)$$$, which define the derangement $$$P$$$. It is guaranteed that $$$P_i \neq i$$$ for all $$$i$$$, and that for any $$$i \neq j$$$, $$$P_i \neq P_j$$$.
Print a single line containing an integer $$$Q$$$, representing the highest possible quality value that can be obtained from the choice of ingredients, following the restrictions defined by the derangement $$$P$$$.
510 5 6 7 82 3 4 5 1
14
42 3 4 53 4 2 1
8
51 4 5 6 75 3 2 1 4
10
João Carlos and Arthur are big streamers in the world of Roblox. They decided to team up for a collaboration event!
Arthur wants to make the best collaboration possible, so he modeled the $$$N$$$ Roblox games he has in common with João as a tree: an undirected, connected, and acyclic graph. To study the impact on the community, he will conduct $$$Q$$$ simulations, where in the $$$i$$$-th simulation, he will ask João to play with his followers the games corresponding to the vertices on the path* from $$$S_i$$$ to $$$F_i$$$.
João currently has $$$M$$$ followers, each identified by a different integer from $$$1$$$ to $$$M$$$ according to their skill in Roblox. During the simulations, to keep the matches interesting, João decided that for every game $$$j$$$, he will play it with all his followers with identifiers from $$$L_j$$$ to $$$R_j$$$. Additionally, since João is a pro player, every follower who plays with him the game $$$j$$$ will immediately gain $$$K_j$$$ aura (those who do not play gain $$$0$$$ aura).
Thus, at the end of simulation $$$i$$$, every follower $$$k$$$ ends up with an accumulated aura $$$A_{i, k}$$$, which is the sum of the auras they gained throughout all the games played by João in that simulation. As part of his analysis, Arthur would like to calculate the result $$$W_i$$$, which is the sum of the accumulated auras of the followers with identifiers from $$$X_i$$$ to $$$Y_i$$$, that is, $$$W_i = \sum_{k = X_i}^{Y_i} A_{i, k}$$$.
However, Arthur needs to do his Studies in Security work. Help him calculate the results $$$W$$$ for all $$$Q$$$ simulations! Since each $$$W$$$ can be very large, you must print the remainder of $$$W$$$ when divided by $$$998244353$$$.
Note that the simulations are INDEPENDENT, meaning the accumulated aura does NOT persist between simulations.
*: In a tree, there is only one path between two vertices that does not pass through the same vertex more than once.
The first line contains two integers: $$$N$$$ $$$(1 \le N \le 5 \cdot 10^4)$$$ and $$$M$$$ $$$(1 \le M \le 10^{9})$$$, representing the number of games and the number of João Carlos's followers.
The next $$$N-1$$$ lines contain two distinct integers $$$U$$$ and $$$V$$$ $$$(1 \le U, V \le N)$$$ indicating that there is an edge between the vertices corresponding to games $$$U$$$ and $$$V$$$.
This is followed by $$$N$$$ lines containing three integers. The $$$j$$$-th line contains $$$L_j$$$, $$$R_j$$$ $$$(1 \le L_j \le R_j \le M)$$$ and $$$K_j$$$ $$$(1 \le K_i \lt 998244353)$$$, the integers associated with game $$$j$$$.
The next line contains an integer $$$Q$$$ $$$(1 \le Q \le 5 \cdot 10^4)$$$, the number of simulations.
Finally, there are $$$Q$$$ lines containing four integers. These integers are encrypted. Let $$$W_{i-1}$$$ be the result of the $$$(i-1)$$$-th simulation (if $$$i = 1$$$, $$$W_{i-1} = 0$$$). Your program will receive $$$S_i \oplus W_{i-1}$$$, $$$F_i \oplus W_{i-1}$$$ $$$(1 \le S_i, F_i \le N)$$$, $$$X_i \oplus W_{i-1}$$$ and $$$Y_i \oplus W_{i-1}$$$ $$$(1 \le X_i \le Y_i \le M)$$$ describing the parameters of the $$$i$$$-th simulation.
Write $$$Q$$$ lines, each containing a single integer. The $$$i$$$-th line should contain $$$W_i$$$: the result of the $$$i$$$-th simulation.
10 103 49 61 94 54 25 67 104 810 16 9 104 6 87 9 11 3 65 7 13 6 15 8 109 9 102 5 46 6 7106 2 2 640 40 45 323 5 9 100 5 3 742 46 46 3844 40 35 3438 37 35 375 5 13 1313 12 2 223 28 17 29
42 0 1 44 43 32 4 10 20 13
$$$\oplus$$$ indicates the XOR (exclusive OR) operation applied bit by bit. For example, $$$3$$$ is $$$0011$$$ in binary, and $$$5$$$ is $$$0101$$$. $$$3 \oplus 5 = 6$$$, which is $$$0110$$$ in binary.
Ivo, a renowned competitor, felt nostalgic about his training with the classic UVa Online Judge and decided to incorporate it into a word search game.
The game is simple: given a matrix of letters, Ivo searches for occurrences of the letter sequence U-V-A, which can occur vertically, horizontally, or diagonally. Create a program that tells how many times Ivo saw the UVa!
The first line presents the dimensions $$$N$$$ and $$$M$$$ of the matrix $$$(3 \leq N, M \leq 100)$$$, separated by a space. The following $$$M$$$ lines each contain $$$N$$$ letters.
Output the number of occurrences of the letter sequence UVa identified by Ivo.
3 3IVOVIUUVA
1
4 5aaaavvvvuuuuvvvvaaaa
16
In the second example, each 'v' has an adjacent 'u' and 'a' vertically, defining $$$8$$$ occurrences of 'UVa'. Additionally, each of the 4 'v's that are not on the edges of the matrix has an occurrence of 'UVa' in each diagonal, resulting in $$$8$$$ more cases for a total of $$$16$$$.
Professor Edson used the University Week to organize a game night with the members of UnBalloon. Since everyone is a competitive programmer, impartial combinatorial games were chosen!
The game in question is played on a grid of cells with $$$N$$$ rows and $$$M$$$ columns (each of the $$$N$$$ rows of the grid has $$$M$$$ cells). Initially, all cells are empty.
Wilson and Pedro are the next pair to play this game, which is played in turns. Wilson starts by playing, and on his turn, he must choose an empty cell and write the letter $$$W$$$ in it (so that it is no longer empty). Pedro must do the same on his turn, but writing the letter $$$P$$$. The player who cannot make a move (when all cells are marked) loses.
Both have devised quite elaborate strategies to outsmart their opponent. Unfortunately, you will not be able to follow the game to the end, but you know that no matter how hard one of the players tries, victory will certainly belong to the other. Which player will be the winner?
The input consists of a single line with two integers: $$$N$$$ and $$$M$$$ $$$(1 \leq N, M \leq 100)$$$, which represent the number of rows and columns of the grid.
Print a line containing $$$W$$$ if Wilson will win the game, or $$$P$$$ if Pedro will win the game. It is guaranteed that one of the players will always win the game, regardless of the opponent's actions.
1 2
P
1 1
W
99 87
W
In the year $$$2087$$$, humanity developed temporal communication technology, allowing messages to be sent to the past. You work at the Temporal Monitoring Center and need to process queries about these messages from the future.
You receive $$$N$$$ messages from the future, each with a timestamp $$$t_i$$$ indicating when the message was originally sent (in the future). Your system needs to respond to $$$Q$$$ queries, where each query asks: "How many messages were sent in the time interval [L, R]?"
First line: two integers $$$N$$$ and $$$Q$$$ $$$(1 \leq N, Q \leq 2 \cdot 10^5)$$$
Second line: $$$N$$$ integers $$$t_i$$$ representing the timestamps of the messages $$$(1 \leq t_i \leq 10^9)$$$
The next $$$Q$$$ lines: two integers $$$L$$$ and $$$R$$$ for each query $$$(1 \leq L \leq R \leq 10^9)$$$
For each query, print the number of messages received in the closed interval $$$[L, R]$$$.
5 310 1 10 7 51 56 102 4
2 3 0
3 310 15 201 510 1015 25
0 1 2
6 5600 500 400 300 200 100100 10050 3501 1000000000401 600700 800
1 3 6 2 0
After many requests, the UnBalloon Minecraft World Championship has finally been announced! In this championship, there are several different categories, with ostentation being one of them. In this category, the winner will be the one who collects the most diamonds.
Adrielly and Nikolle decided to team up to compete in this category and, to showcase their power, they are willing to collect enough diamonds to build a super tower and activate a beacon up there.
A tower is made up of diamond blocks, where the $$$i$$$-th level consists of $$$(2i + 1)^2$$$ blocks. That is, the first level consists of $$$9$$$ blocks, the second level consists of $$$25$$$ blocks, the third level consists of $$$49$$$ blocks, and so on.
Adrielly and Nikolle are determined to build a tower of height $$$N$$$. At the moment, they are mining and have forgotten to count how many blocks will be needed! Can you help them?
The input contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^{18}$$$), the desired height of the tower.
Print, on a single line, the number of blocks needed to build a tower of height $$$N$$$ modulo $$$10^9 + 7$$$.
1
9
3
83
5
285
3271897334534761
217325831
In the figure below, we have towers with heights $$$4$$$, $$$3$$$, $$$2$$$, and $$$1$$$, respectively.
The cycle for the next Exatas Cup has already begun, and Cauê, the maestro of Selecic, is already thinking about new tactics to pursue the title in the next edition.
Cauê is considering organizing the team in a positional manner, where each player must operate in a restricted tactical area of the field according to their role. For example, forwards should operate near the opponent's goal, defenders in the team's defensive area, and the goalkeeper only in the area restricted to the goal. However, the idea of a role can be quite complex: within the space reserved for a role, there can be other roles contained within it!
For example, within the forwards' space, there may be a space reserved for wingers and for center-forwards. And also within the wingers' space, there can be a space for those with inverted feet and those with natural feet. Roles can be nested within others arbitrarily! However, there cannot be two roles that share space unless one is contained within the other — this would go against Cauê's tactical principles.
To illustrate his idea, Cauê used a Cartesian plane to draw the tactical regions. Each region was represented by a simple convex polygon, such that the edges of polygons from different regions do not intersect. This ensures that, between different regions, either they do not intersect or one is strictly contained (i.e., "inside") the other.
The other members of Selecic were quite confused by Cauê's drawing. A recurring question was: "If I want to start playing at point $$$(X, Y)$$$, how many roles will I have to perform in the game? That is, how many roles contain the point $$$(X, Y)$$$?". After all, the players on the team do not have the capacity to perform too many roles in the match...
Cauê is busy watching the Vasco game, and therefore asked you to take his place in answering the questions from the Selecic players! He has suffered enough with this team, so it doesn't hurt to do him this favor.
The first line of the input contains two integers: $$$N$$$ and $$$Q$$$, representing respectively the number of regions drawn by Cauê and the number of questions from the players.
The following lines contain the descriptions of the polygons of each of the $$$N$$$ regions. The description of the $$$i$$$-th polygon starts with a line containing the integer $$$k_i$$$: the number of vertices of the polygon. The next $$$k_i$$$ lines each contain two integers $$$X$$$ and $$$Y$$$, representing the Cartesian coordinates of a vertex of the polygon. The vertices are given in counterclockwise order, and there are no three consecutive collinear vertices.
Then, the next $$$Q$$$ lines each contain two integers $$$X$$$ and $$$Y$$$, representing the Cartesian coordinates of the points associated with the players' questions.
It is guaranteed that the edges of the polygons do not intersect. Additionally, it is guaranteed that the points of the questions are not vertices nor are they on the edge of any of the polygons in the input. Finally, all points in the input are distinct.
It is also guaranteed that $$$N, Q \geq 1$$$, $$$k_i \geq 3$$$, $$$-10^9 \leq X, Y \leq 10^9$$$, and that $$$(Q + \sum_{i=1}^n k_i) \leq 6 \cdot 10^5$$$.
Print $$$Q$$$ lines: on the $$$i$$$-th line, the number of regions that contain the point from the $$$i$$$-th question.
1 24-1 00 -11 00 10 01 1
1 0
3 341 43 29 82 631 011 90 842 53 36 63 63 52 41 3
3 2 1
Professor John was at sea, conducting research on marine fauna, when his boat, which was anchored at point $$$X$$$, was enveloped by a thick fog that interfered with both visibility and the boat's location sensors.
John and his team waited patiently for two days, but as there was no indication that the fog would lift and their supplies were running low, he decided they should search for land.
To avoid sailing aimlessly in a disoriented manner, the professor devised the following strategy:
It was a long and exhausting process, but the team succeeded and anchored on solid ground. After recovering, Professor John retrieved the record from his logbook, which stated that the total displacement of the boat was $$$D$$$ meters and the point where they found land was located at $$$Y$$$.
From this data, he intends to determine the point $$$X$$$ where they were initially anchored. However, given the physical and mental exhaustion from the experience, John may have made mistakes in his notes. Therefore, help determine whether the data is consistent or not, and if so, find the value of $$$X$$$.
The first line of the input contains the integer value $$$D$$$ $$$(1\leq D\leq 3\times 10^{18})$$$.
The second line of the input contains the integer value $$$Y$$$ $$$(-10^{18}\leq Y\leq 10^{18})$$$.
Print, on one line, the message "Sim" (without quotes) if Professor John's data is consistent, or the message "Nao" if it is not.
If the data is consistent, print on the second line the value of $$$X$$$, the point where the boat was initially anchored.
1010
Sim 6
52
Nao
401
Sim -9
4-3
Sim -1
In the first case, we have the following sequence of movements of the boat: the numbers in blue and the arrows indicate the total displacement to the indicated point, the numbers in black mark the positions, and the flag signals the beginning of solid ground.
In the second case, to reach point $$$2$$$ with a displacement of exactly $$$5$$$ meters, the boat should have been anchored at $$$X = 3$$$, and we would have the following situation:
Note that, as shown in the figure, if solid ground began at point $$$Y = 2$$$, the boat would have reached it when the total displacement recorded was $$$3$$$ meters, thus Professor John's record is inconsistent.
In the fourth case, note that both $$$X$$$ and $$$Y$$$ can be negative.