TFG was watching the chess world's championship with his brother VH and they got in the mood to play chess. VH learned an opening move called "sicilian", but TFG didn't like it, because VH didn't understand the suffering that the knight had to bear. To get VH to understand that, TFG used an application made for cellphones that he created that was able to turn his brother into a chess's knight. However, due to an unknown bug, his brother got stuck on the cellphone's numerical keypad, instead of being trapped on a chess table. TFG quickly fixed the bug, but since his brother was suffering, he told his brother that would only turn him back into his human shape if he solved the following problem:
"How many distinct phone numbers $$$S$$$, of length $$$N$$$, can he create by moving as a horse on the keypad, starting on the number $$$K$$$?"
VH must start on the position $$$K$$$ (without pressing this key), and then he must move to a position that could be reached by a chess knight, if the keypad was a chess table. When he moves to another position, the key of this position is pressed and the digit is added to the string. He keeps going until the $$$N$$$ digits are stored.
However, TFG said that this problem was actually pretty easy. To make things more interesting, he told his brother another number $$$T$$$, of length $$$M$$$, and wants to know how many different numbers $$$S$$$ can he create, of length $$$N$$$, such that there is no occurrence of $$$T$$$ in $$$S$$$ (i.e. $$$T$$$ is not a substring of $$$S$$$).
The cellphone keypad has the following shape:
$$$1 2 3$$$
$$$4 5 6$$$
$$$7 8 9$$$
$$$. 0 .$$$
($$$.$$$ denotes an invalid position)
Since the chess knight moves on $$$L$$$-shaped paths (two moves in one direction and one move on the other one). For example, from the position $$$1$$$ he could go to $$$6$$$ or $$$8$$$.
Since the answer can be very large, you must output its remainder when divided by $$$10^9 + 7$$$.
The first line contains three integers $$$N$$$, $$$M$$$ and $$$K$$$ ($$$1 \le N \le 10^4$$$, $$$0 \le M \le 100$$$ e $$$0 \le K \le 9$$$). The second line contains a string $$$T$$$, representing a phone number, with $$$M$$$ digits ($$$0 \le T_i \le 9$$$).
You must output a single number, the amount of distinct phone numbers of $$$N$$$ digits that doesn't contain $$$T$$$ as a substring, modulo $$$10^9 + 7$$$.
2 2 0 40
5
3 2 0 40
10
In the first sample, the possible numbers are: $$$43$$$, $$$48$$$, $$$60$$$, $$$61$$$ and $$$67$$$. Despite the horse being able to create the number $$$40$$$ starting from $$$0$$$, it is not a valid phone number due to the given restrictions.
Many thousand years ago, stories of a man, known as Ben-10's lost brother, got spread throughout the world. Legend says that he, whose name is Beza-10, was a very peculiar guy, with jaw-dropping abilities and powers. Due to that, Ben-10 got afraid that his brother would become more famous and powerful than him, so he decided to banish Beza from the dimension we live in.
Years passed, and now Beza is planning his return, so he can finally get the revenge he wanted ever since he was banned. However, travelling on different dimensions is not as simple as he thought it would be, therefore, he needs your help.
Beza-10 is trapped on a dimension represented as a $$$N$$$x$$$M$$$ grid. Because the spell cast on him was so powerful, the grid got filled with many traps, denoted by the character #, on which he can't step on, because if he did, he would suffer tremendous pain and probably die. Therefore, he can only walk on empty spaces.
Just like Ben-10, Beza possesses a magical watch, which is capable of shapeshifting him into powerful forms. However, as he is on an unknown dimension, his watch no longer works as expected: he can only shapeshift into chess pieces, except the pawn. After shapeshifting into a chosen chess piece, he will move according to the rules of this specific piece, which are just like in normal chess:
- The queen can move in any direction she wishes (vertically, diagonally or horizontally);
- The tower can move in every direction, except diagonally;
- The king can move to any of the $$$8$$$ closest points that surround him;
- The bishop can only move diagonally;
- The knight can move to any point that, together with the knight's position, makes a $$$L$$$-shaped path, i.e. the path from one point to another will contain three steps, strictly on this sequence: one on the horizontal axis, and two on the vertical axis (or the opposite - two on the horizontal and one on the vertical);
- A movement consists only on moving from one point to another, discarding its distance. That means that going from $$$(X_1, Y_1)$$$ to $$$(X_2, Y_2)$$$ defines a single movement, no matter how far apart they are from each other. Shapeshifts don't count as a movement;
- Here, chess pieces can't move from one point to another if there is one or more traps along the path or on the arrival point. The knight, though, is an exception: his movement is, essentially, a "jump": traps on the path will be ignored. However, he cannot jump to a point if it contains a trap. Also, Beza cannot move to a point outside the grid, as he would fall into infinity and never be seen again.
Also, Beza is scared that the excessive use of his watch will break it, and, therefore, decided that he will use it at most $$$K$$$ times.
Initially, assume that Beza has the form of the king chess piece, is located on the position of the grid that contains the character 'B', and wishes to reach the escape portal, marked with a 'P' on the grid. He asks you what is the minimum number of movements he will require in order to escape, doing at most $$$K$$$ shapeshifts, or report that it is impossible.
The first line of input has three integers: $$$N$$$ and $$$M$$$ ($$$2 \le N, M \le 100$$$), the grid dimensions, and $$$K$$$ ($$$0 \le K \le 100$$$), which is the maximum amount of shapeshifts Beza is willing to do. The next $$$N$$$ lines contain $$$M$$$ characters each, which can be: a 'B', denoting the starting position of Beza-10, a 'P', the position of the escape portal, a '#', which is a trap, or a single dot $$$.$$$, which is a free space that Beza can step on.
The output consists of a single integer, which is the minimum number of movements needed to reach the portal, doing at most $$$K$$$ shapeshifts. If it is not possible to reach the portal with the given grid and conditions, print $$$"$$$-1$$$"$$$ (without quotes).
3 3 3 B.. .## .#P
2
7 5 3 B..#. .#..# #...# ..... .#.#. #.#.# ..P..
3
There are $$$n$$$ islands laid out on a circle. An agency is responsible for the control of a set of $$$m$$$ bidirectional bridges, numbered from $$$0$$$ to $$$m-1$$$, that are located on the center of the islands and can join any two pair of them. The agency might need to restrict traffic on some bridges in case that maintenance is needed to ensure safety of everyone who crosses it. When that happens, the agency select a subset of bridges to be free for crossing. Besides that, it is needed to know if it is possible to go from one given island $$$a$$$ to another island $$$b$$$ using only those bridges, so that the population can plan their trips accordingly.
The agency must process $$$q$$$ queries, which have four types:
- 1 $$$l$$$ $$$r$$$ — make only bridges from the interval $$$[l, r]$$$ free to be crossed.
- 2 $$$l$$$ $$$r$$$ — make all bridges free to be crossed, except those that belong to the interval $$$[l, r]$$$. Note that here, bridges belonging to the interval $$$[l, r]$$$ will go under maintenance, while the ones outside it will become free to be crossed, even the ones who were previously under maintenance.
- 3 $$$x$$$ $$$u$$$ $$$v$$$ — change the $$$x$$$-th bridge, so that it connect the islands $$$u$$$ and $$$v$$$.
- 4 $$$u$$$ $$$v$$$ — check if there exists a path between islands $$$u$$$ and $$$v$$$ using only bridges that are not under maintenance.
At the beginning, all bridges are free.
Latache, a student at CIn, while doing his internship at this agency, he received the task of creating a program capable of quickly processing the given queries. However, since Latache was called for so many internships, he didn't have enough time to complete the task before going to work on a different country. But Latache knows how good you are at programming, so you must help him and not let him down (otherwise, he won't help you get interviews).
The first line contain $$$3$$$ integers $$$n$$$, $$$m$$$ and $$$q$$$ $$$(2 \le n \le 250, 1 \le m \le 10^5, 1 \le q \le 2 \cdot 10^4)$$$.
Then, $$$m$$$ lines follow, containing a pair of numbers $$$a_i$$$, $$$b_i$$$ $$$(0 \le a_i, b_i \lt n, a_i \neq b_i)$$$, indicating the pair of islands connected by the $$$i$$$-th bridge.
Finally, we have $$$q$$$ more lines: the requisitions, according to the description given on the statement, with the following restrictions:
$$$0 \le l \le r \lt m$$$
$$$0 \le x \lt m$$$
$$$0 \le u, v \lt n, u \neq v$$$
Your program must output, after each query of types 1, 2 and 3, the number of connected components on the graph formed by the islands and bridges, considering only the bridges that are not under maintenance.
For queries of type 4, output "YES" or "NO" (without quotes).
6 5 5 0 1 1 2 5 4 4 5 5 4 1 0 4 4 5 4 4 5 2 3 2 1 3 3 4 1 4
3 YES NO 2 1
Naum's cellphone has a keypad just like on the image below. When he's typing someone's name, Naum needs to press just once the key that contains the letter which he's typing at the moment.
Everyone was very impressed by this amazing functionality, except for you. So, Naum challenged you to solve this problem, if you really want to prove that this functionality isn't that awesome after all.
Given a list of $$$N$$$ Naum's cellphone contacts and $$$Q$$$ sequences of pressed keys, you must answer, for each sequence, the number of contacts whose name could actually be being typed by Naum.
Formally, Naum could be typing a name $$$s$$$ with the sequence of letters $$$t$$$ if there is a replacement of the keys in $$$t$$$ for the letters they represent, resulting in string $$$t'$$$, where $$$t'$$$ is a prefix of $$$s$$$.
The first line of input contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le Q \le 2 \cdot 10^5$$$), being the size of Naum's cellphone contact list and the number of sequences to be analyzed, respectively.
Then, $$$N$$$ lines follow, where the $$$i$$$-th of them contain a string $$$s_i$$$ $$$(0 \lt s_i \le 10 ^ 5)$$$, the name of the $$$i$$$-th contact, which consists only in lowercase english letters, from A to Z.
Finally, $$$Q$$$ lines follow, where the $$$i$$$-th of them contains a string $$$t_i$$$ ($$$0 \lt t_i \le 10^5$$$), the $$$i$$$-th sequence of keys typed by Naum, which consists of numbers from $$$0$$$ to $$$9$$$ (inclusive).
It is guaranteed that $$$\sum_{i=1}^{N} |s_i| \le 10^6$$$ and $$$\sum_{i=1}^{Q} |t_i| \le 10^6$$$.
You must output $$$Q$$$ integers, the answer for each one of the given sequences of keys.
5 5 amanda diogo lucas carlos gabriel 2 3 234 34 22
2 1 0 1 1
The holidays are coming and everyone is anxiously waiting to see the festive decorations of the Informatics Center, which will be planned by Mendes. Particularly, Mendes favorite part is preparing the christmas tree. We can see, by looking at his websites, that Mendes is very picky about the beauty of the things made by him. As for the christmas tree, he believes that its beauty is directly proportional to its size. The beauty of a christmas tree can be understood as the expected length of a random path on that tree. In mathematical terms, a tree is a connected acyclic graph. A path on a tree is the set of edges on the only simple path that connects two vertexes. The length of a path is the number of edges in it. Now, you must help Mendes to choose the best christmas tree for the Informatics Center! Your job is to calculate the expected value of the length of a random path on a given tree. The expected value of a random path on any tree can be expressed as $$$\frac{P}{Q}$$$, where $$$P$$$ and $$$Q$$$ are coprimes. Your program must compute the value of $$$PQ^{-1}$$$ $$$mod$$$ $$$10^{9} + 7$$$.
On the first line, there will be an integer $$$N$$$ $$$(1 \le N \le 200000)$$$, the number of nodes on the tree. Then, $$$N-1$$$ lines follow, each one of them containing two integers $$$A$$$ and $$$B$$$ $$$(1 \le A, B \le N)$$$, representing an edge connecting the vertexes $$$A$$$ and $$$B$$$.
You must output a single line, containing the value of $$$PQ^{-1}$$$ $$$mod$$$ $$$10^{9} + 7$$$, where $$$\frac{P}{Q}$$$ expresses the value of the expected length of a random path on the given tree, and $$$Q^{-1}$$$ is the modular inverse of $$$Q$$$ modulo $$$10^{9} + 7$$$.
5 1 2 2 3 3 4 4 5
333333337
4 1 2 1 3 1 4
300000003
A random path on a tree can be seen this way: we randomly pick two vertexes (not necessarily distinct) from the tree and select the edges which are in the path that connects those two vertexes.
Fairy is a very excentric mailman. Every now and then, he likes to change some correspondences that he is responsible for, swapping than to different addresses, as he enjoys the consequent turmoil. One day, Fairy was in his most inspired self and decided to swap all correspondences from their original addresses. No address should receive its intended correspondence. It will be Fairy's ultimate masterpiece. Although he is keen to chaos, Fairy is also a very curious person, and he asked himself about how many ways he could swap the correspondences so none of the addresses receive the correct message. As he's very lazy, he decided to ask your help to fulfill his objectives. You'll receive an integer number $$$N$$$, that stands for the correspondences amount, to which you should generate another integer $$$S$$$ that stands for the amount of ways he can swap the correspondences. Help Fairy in his mischievous plan, or he might change your correspondence as well.
A unique integer $$$N$$$, ($$$1 \le N \le 20$$$) standing for the amount of correspondences.
A unique integer $$$S$$$, representing the amount of ways Fairy can swap the correspondences. As the possibilities amount can be very big, the answer should be given as $$$S$$$ $$$mod$$$ $$$10^9+7$$$.
3
2
Pedro and Lucas are two brothers who look extremely alike in many ways, despite not being twins. One day, their friends Gabriel Mendes and Gabriel Pessoa decided to know, once and for all, if they really looked that similar, and, for that, they asked for the brothers to go for a walk on the park. They will walk the same total distance, but doing random moves. Therefore, in order to actually know the path traveled by them, Pedro and Lucas need to write their positions on every change of direction they make, or simply mark their current position whenever they wanted, until they decided to stop.
Mendes and Pessoa now decided to analyze the trajectory that was created by the movements of each of the brothers, and the result was really impressive!
Let us call each of the $$$N$$$ points marked by Pedro as $$$P_{i}$$$, and the $$$M$$$ points marked by Lucas as $$$L_{i}$$$. They verified that for each two consecutive points on each of the brothers' path (i.e. the segments $$$[P_{i}, P_{i + 1}]$$$ and $$$[L_{i}, L_{i + 1}]$$$), the distance between them were equal. That is,
That also implied that the brothers actually marked the same number ($$$K$$$) of points. How crazy is that?
Mendes and Pessoa were so impressed that they thought:
Your goal is to print the minimum number of points that would need to be marked on the path of each one of the Gabriels (Mendes and Pessoa), so that every distance between consecutive points on their paths would be exactly the same.
The first line of input consists of two integers $$$N$$$ and $$$M$$$, $$$[2 \leq N, M \leq 20\,000]$$$, that represent, respectively:
$$${\: \displaystyle \bullet \:}$$$ The number of points marked by Mendes;
$$${\: \displaystyle \bullet \:}$$$ The number of points marked by Pessoa;
The following $$$N$$$ lines contain the points $$$P_{i}$$$ marked by Mendes $$$[-10^{9} \leq x_{P_{i}}, y_{P_{i}} \leq 10^{9}]$$$;
A blank line separates the lists of points of Mendes and Pessoa;
Then, the next $$$M$$$ lines contain the points $$$Q_{i}$$$ marked by Pessoa $$$[-10^{9} \leq x_{Q_{i}}, y_{Q_{i}} \leq 10^{9}]$$$;
The output consists of one integer: The minimum number of points that need to be added on Mendes' path and Pessoas' path.
5 3 0 0 3 0 3 4 6 4 6 8 0 0 6 8 10 8
2
- The points coordinates may not be integers;
- Two distances can be considered equal if $$$abs(D_{a} - D_{b}) \leq 10^{-5}$$$;
- The length of each segment must be equal in both paths.
Diogo is quite a guy. Someone that scares people around the Informatics Center, specially Mendes. One day, Mendes gave him a graph challenge, since Diogo claims to be the Graph Theory Master. Just like Math Masters are challenged to solve large multiplications using only the brain, the challenge received by the Graph Theory Master was as follows:
"Given an undirected graph, without multiple edges or self loops, and two arbitrary vertices $$$u$$$ and $$$v$$$. You must build a path from $$$u$$$ to $$$v$$$ with length $$$K$$$ and yell that path out loud without a single mistake."
Anxious to get his revenge, and since there can be many different valid paths, Diogo swore to haunt Mendes' dreams, reciting one different path every night, so that he never doubted his algorithmic skills ever again. In order for Mendes to see what is coming after him, you must write a program that answers for how many nights he won't be able to sleep in peace, i.e in how many distinct paths there are that satisfy the restrictions above. Since this number can be very large, output its remainder on the division by $$$D$$$, on a desperate attempt of relieving Mendes of this terrible burden. If Diogo is not able to build even a single set, your program must print "Mendes will sleep in peace." (without quotes)
P.S.:
- It is possible to have repetitions of vertices and/or edges in a path.
- The length of a path is the number of edges in it.
The first line consists of three integers $$$N$$$, $$$M$$$ e $$$D$$$ ($$$1 \le N \le 10^2$$$, $$$0 \le M \le \frac{N(N - 1)}{2}$$$, $$$100 \le D \le 10^9+7$$$), the number of nodes in the graph, the number of edges in the graph and the divisor that should be utilized to print the answer, respectively.
The second line consists of three integers $$$K$$$, $$$u$$$ e $$$v$$$ ($$$0 \le K \le 10^{18}$$$, $$$0 \le u, v \lt N$$$), the path length, the beginning and the ending of the path that you should find.
Then, $$$M$$$ lines follow describing the graph edges, where the $$$i$$$-th of them contains two integers $$$u_i$$$, $$$v_i$$$ ($$$0 \le u_i, v_i \lt N$$$, $$$u_i \neq v_i$$$), describing the that there is an edge between vertex $$$u_i$$$ and $$$v_i$$$.
Your program must output a single integer, the number of distinct ways Diogo can build a path of length $$$K$$$ between the two given vertexes, modulo $$$D$$$. If he can't build even a single set, your program must output "Mendes will sleep in peace." (without quotes).
5 5 10000 2 0 4 0 1 1 2 2 3 1 3 3 4
Mendes will sleep in peace.
3 3 10009 3 0 1 0 1 2 0 1 2
3
3 1 100 2 0 0 0 1
1
There are $$$N$$$ different types of pieces, numbered from $$$1$$$ to $$$N$$$, the $$$i$$$-th of them having length $$$L_{i}$$$ and, for each type, there are exactly $$$10^9$$$ pieces of it. A tower is a sequence of pieces, where the tower's height is the summation of the lengths of the pieces in it.
You just made two new friends: Serra and Beza! They have towers of height $$$A$$$ and $$$B$$$, respectively. If the height of their towers is different, one of them becomes sad. Therefore, in order to help your friends, you decided you're gonna distribute some pieces in such a way that the height of their towers become equal. Show the set of pieces that must be given to each one of them.
The first line of input contain two integers $$$A$$$ and $$$B$$$ $$$(1 \leq A, B \leq 10^{9})$$$, representing the initial height of the towers of Serra and Beza, respectively.
The second line contains an integer $$$N$$$ $$$(1 \leq N \leq 10^{5})$$$, the number of different types of pieces.
The third line contains $$$N$$$ integers $$$L_{i}$$$ $$$(1 \leq L_{i} \leq 10^{4})$$$, where $$$L_{i}$$$ is the length of the pieces of the $$$i$$$-th type.
You must output two blocks of $$$N$$$ lines each. The first line contains the set of pieces given to Serra, and the second line, the set of pieces given to Beza.
The $$$i$$$-th line of the first block must have a single integer $$$a_{i}$$$, denoting the number of pieces of the $$$i$$$-th type you must give to Serra.
The $$$i$$$-th line of the first block must have a single integer $$$b_{i}$$$, denoting the number of pieces of the $$$i$$$-th type you must give to Beza.
Note that the output must obey $$$a_{i} + b_{i} \leq 10^{9}$$$, for all $$$i$$$ $$$(1 \leq i \leq N)$$$.
It is guaranteed that there is always an answer. If there is more than one correct solution, you can output any of them.
3 8 2 3 4
3 0 0 1
Joseph developed a device that allows people to decrease or increase their height by at most $$$D$$$ units. He's playing with his friend Lucas on a circuit with N houses, numbered from $$$1$$$ to $$$N$$$, on which Lucas can only get inside if his height is exactly equal to the height of the door of the house he's trying to get in. There will be two types of queries:
1. There will be given two integers $$$i$$$ and $$$X$$$, meaning that the i-th house's height is now equal to $$$X$$$;
2. There will be given two integers $$$L$$$ and $$$D$$$, meaning that Joseph's device can only increase or decrease someone's height by at most $$$D$$$ units, and that Lucas will walk sequentially through the circuit, starting with height equal to $$$A[L]$$$, on the $$$L$$$-th house, until he finishes the circuit or encounters a house where he can't get in. For each query of this type, you must answer on which house he will stop. Note that Lucas can only go to house $$$i+1$$$ from the house $$$i$$$ if $$$|A[i + 1] - A[i]| \leq D$$$.
The first line contains one integer $$$N$$$ $$$(1 \leq N \leq 2*10^5)$$$, representing the number of houses on the circuit. The second line contains $$$N$$$ integers $$$A_i$$$ $$$(1 \leq A_i \leq 2*10^5)$$$, where $$$A_i$$$ is the height of the door of the $$$i$$$-th house. The third line contains a single integer $$$Q$$$ $$$(1 \leq Q \leq 2*10^5)$$$, the number of queries. Then, $$$Q$$$ lines follow, each of them containing three integers: $$$t_i$$$ $$$(1 \leq t_i \leq 2)$$$, $$$a_i$$$ and $$$b_i$$$ $$$(1 \leq a_i \leq N, \ 1 \leq b_i \leq 2*10^5)$$$. $$$t_i$$$ stands for the type of $$$i$$$-th query, and $$$a_i$$$ and $$$b_i$$$ are the $$$i$$$-th query's parameters, according to the description on the problem's statement.
For each query of the second type, output one line containing a single integer, representing the number of the house where Lucas will finish his walk.
5 1 3 5 7 9 5 2 1 2 2 1 1 1 5 100 2 1 2 2 1 100
5 1 4 5
Clodes is a student that is crazy about K-pop like no other person in the world. He has a grandma who loves him a lot and wishes to reward him for his outstanding grades and performance on his studies. To do so, his grandma decided to give him a gift: she will pay for him and his friends to attend a K-pop event, that is going to happen in another city.
Clodes, then, while planning his trip, was looking through a total of $$$N$$$ different cities, when he found $$$M$$$ available flights connecting two cities, where the $$$i$$$-th of them leaves from city $$$u_i$$$, lands at city $$$v_i$$$, costs $$$P_i$$$ taokeis (the currency of Clodes' country) and has $$$A_i$$$ available seats on the plane. Clodes doesn't want to be apart of his friends, therefore, all of his friends must go on the same flight as him. Therefore, Clodes seeks a sequence of flights starting at $$$O$$$, the city he lives in, and ends at $$$D$$$, the city where the K-pop event wil happen. Every flight of this sequence must have room for all his friends.
There is one more thing. Clodes loves number theory. Even more than his friends do. Because of that, he decided that he wants to take a prime number of friends on the trip with him, including himself on that count, because Clodes considers himself his friend.
But life is not easy, specially for Clodes, since he chose to do his graduation on Computer Engineering, instead of Computer Science. He is full of exams this week and needs to study, thus, he doesn't have any more time available to plan his trip and wants your help. He wants you to calculate the minimum amount of money his grandma needs to spend in order to get him and his friends to the event, where the total number of people (Clodes and his friends) is the highest prime possible.
To help you with your difficult task, Clodes decided to formalize the problem before going to study:
- A sequence $$$O \Rightarrow D$$$ is a sequence of flights that starts on the city $$$O$$$ and ends on the city $$$D$$$, representing, then, a way of Clodes getting from his city to the event
- A sequence $$$O \Rightarrow D$$$ with $$$X$$$ seats means that every flight taken on this sequence must have $$$A_i \ge X$$$ available seats
- The cost of a sequence is the sum of prices of all flights used on it
- The cheapest sequence $$$O \Rightarrow D$$$ with $$$X$$$ seats is the one with minimum cost
- The number $$$V$$$ of friends Clodes will bring with him is the maximum prime number $$$V$$$, such that there exists a sequence $$$O \Rightarrow D$$$ with $$$V$$$ seats. In case there is no sequence that fulfills those requirements, then Clodes will be very sad and $$$V$$$ will be $$$0$$$. But he desperately wants to go to this event, therefore, if there is no answer to his problem, but exists a sequence $$$O \Rightarrow D$$$ with $$$1$$$ seat, Clodes will go by himself (i.e., $$$V$$$ will be equal to $$$1$$$), even though $$$1$$$ is not a prime number.
- The total value $$$T$$$ his grandma will spend is going to be $$$0$$$, if Clodes can't make it to the event, or the cost of the cheapest sequence $$$O \Rightarrow D$$$ with $$$V$$$ seats multiplied by $$$V$$$, since she's going to pay for all of his friends too.
Warning: large input, it is recommended to use fast I/O.
The first line of input contains four integers $$$N$$$, $$$M$$$, $$$O$$$ and $$$D$$$ ($$$2 \le N \le 10^5$$$, $$$0 \le m \le 5 \cdot 10^5$$$, $$$1 \le O, D \le N$$$, $$$O \ne D$$$), being, respectively: the number of cities, the number of available flights, the city Clodes lives in and the city on which the event will hapen.
Then, $$$M$$$ lines follow, where the $$$i$$$-th of them contains four integers $$$u_i$$$, $$$v_i$$$, $$$A_i$$$, $$$P_i$$$ ($$$1 \le u_i, v_i \le N$$$, $$$u_i \ne v_i$$$, $$$1 \le A_i, P_i \le 5 \cdot 10^6$$$), representing, respectively, the city of departure, the city of arrival, the number of available seats and the cost of the ticket (in Taokeis) of the $$$i$$$-th flight.
Your program must output two integers: the number $$$V$$$ of friends Clodes will take with him on his trip, and the total value $$$T$$$ his grandma will pay so that this trip can happen.
4 5 1 4 1 4 4 6 1 3 7 1 3 4 2 2 1 2 3 2 2 4 5 3
3 15
4 2 1 4 1 2 3 4 3 4 7 3
0 0
Once upon a time, on a certain university's center, there was a thief that kept stealing grated cheese from the kitchen's fridge. As time passed by, he also began to steal lunch boxes.
It is known that on the beginning of a certain day, all students put their lunch boxes on the fridge, and then, each student will retrieve its lunch box on a specific moment in time to eat it.
Besides that, each lunch box has a warning level, that is a value which depends on many factors (e.g.: in case the student likes to complain on the center's e-mail, the warning level is quite high). The lunch boxes also have a taste level, which ranks how good they are.
Therefore, the thief wants to know, in case he decides to steal at some moment in time, the maximum level of taste he can get, without letting the warning level exceed a given limit, because, if this limit happen to be exceeded, the center will adopt some measures in order to stop the thievery, something that the thief certainly does not want.
The total taste and warning levels are, respectively, the sum of the tastiness and the sum of the warning levels of all the lunch boxes the thief plans on stealing at that moment.
If it happens that a student goes to retrieve his lunch box on the same time the thief goes to steal the fridge, the thief will then wait for the student to retrieve his lunch box and then proceed to rob the fridge.
The first line of input contains two integers $$$N$$$ and $$$Q$$$ ($$$0 \le N \le 10^4$$$, $$$1 \le Q \le 2 \cdot 10^5$$$), the number of lunch boxes and the number of moments in time that the thief can go rob the fridge, respectively.
Then, $$$N$$$ lines follow, where the $$$i$$$-th of them contains three integers $$$V_i$$$, $$$W_i$$$ and $$$E_i$$$ ($$$0 \le V_i \le 10^5$$$, $$$0 \le W_i \le 10^6$$$ e $$$1 \le E_i \le 10^9$$$), the tastefulness level, the warning level and the time at which the $$$i$$$-th lunch box is retrieved from the fridge, respectively.
Finally, there will be $$$Q$$$ more lines, where the $$$i$$$-th of them contains two integers $$$T_i$$$ and $$$K_i$$$ ($$$0 \le T_i \le 10^9$$$, $$$0 \le K_i \le 10^4$$$), representing the moment in time where the thief will go rob the fridge and the warning level limit on that moment.
Your program must output $$$Q$$$ lines, the $$$i$$$-th of them containing a single integer, representing the highest tastefulness level the thief can obtain at the moment $$$T_i$$$, without letting the warning level exceed $$$K_i$$$.
3 2 3 1 1 2 2 3 1 3 4 0 4 2 4
5 2
As you already know, since it is not that unusual, John has two friends that were born on the same day. He bought a magical necklace to give out as a birthday gift to them. This necklace is made of jewels of two colors ($$$A$$$ and $$$B$$$), and allows you to make two cuts. After the cuts, John can create a new necklace with each of the two resulting pieces.
John would like to make two cuts on the necklace in such a way that the two resulting necklaces had the same amount of jewels of each color, that is, the number of jewels of color $$$A$$$ is equal on both necklaces, and the same goes for color $$$B$$$.
The necklace can be represented as a string $$$s$$$, containing only characters $$$A$$$ and $$$B$$$, and each of the cuts can be represented by an integer $$$x$$$ $$$(1 \le x \le |s|)$$$, denoting that the cut was made exactly before the $$$x$$$-th jewel of the string. Note that a necklace has a circular structure, so, the last jewel comes exactly before the first one.
The input consists of a single line containing a string $$$s$$$ $$$(0 \lt |s| \le 10^5)$$$, representing the necklace.
On the first line of the output, print $$$"$$$YES$$$"$$$ (without quotes) if its possible to cut the necklace according to John's wishes and $$$"$$$NO$$$"$$$ (without quotes) otherwise. In case its possible, the second line must have $$$2$$$ integers, indicating the position of each cut John must make. You can output the indices of the cuts in any order you'd like, and, in case there is more than one solution, you can output any of them.
AAAAAAA
NO
AABB
YES 2 4
BBAABABBBAAAAAA
NO
BB
YES 1 2