Abu Shehab, a first-time train traveler and a man who'd spent his entire life in a village without so much as a donkey cart, found himself overwhelmed by the city's central train station and everywhere he looks, there's platforms.
To his LEFT, platforms are numbered from $$$a$$$ to $$$b$$$. To his RIGHT, they're $$$c$$$ to $$$d$$$. And STRAIGHT ahead, all of the other platforms exist.
Abu Shehab was trying to find his way back to Harat Al-Dab3, he's got his ticket with him and it says go to platform $$$e$$$, can you help Abu Shehab reach his platform.
The first line of the input contains an integer $$$T$$$ $$$(1 \le T \le 10^4)$$$ — denotes the number of testcases.
The second line of input contains 5 integers $$$a$$$ and $$$b$$$ $$$(1 \le a \lt b \le 10^5)$$$, $$$c$$$ and $$$d$$$ $$$(b + 1 \le c \lt d \le 10^5)$$$ and $$$e$$$ $$$(1 \le e \le 10^5)$$$ – such that $$$a$$$ and $$$b$$$ denotes the range that you find when you go left, $$$c$$$ and $$$d$$$ denotes the range you find when you go right, and $$$e$$$ denote your destination.
Print $$$T$$$ lines either LEFT if Abu Shehab has to go left, RIGHT if Abu Shehab has to go right, or GO if he has to go straight.
43 6 9 10 41 5 7 10 81 3 7 10 21 3 7 10 4
LEFT RIGHT LEFT GO
Abu Shehab in the train station.
Abu Adel, the famous storyteller at Abu Hatem's coffee shop, decided to write his own fictional stories and sell them. So, he went and bought a magical Nokia 3311 to write stories faster.
The magical Nokia 3311 has $$$k$$$ keys, each of which is used to type several characters. Each lowercase English letter is assigned to exactly one key.
Nokia 3311* Abu Adel authored an amazing fictional story about smartphones that use touch screens instead of keys. However, despite writing a remarkable story, he forgot to save his work, and all of it was lost.
Fortunately, he has a key logger. By reviewing the logs, he hopes to retrieve the original text.
Abu Adel knows $$$n$$$ English words. When he examined the logs, he found that he had written $$$m$$$ words, but for each word, he only knows the pattern of the keys he pressed rather than the exact characters.
Now, for each of the $$$m$$$ patterns, Abu Adel wants to determine how many of the $$$n$$$ words he knows can be formed using that pattern. This will help him narrow down the possibilities and recover the original text.
The first line contains three integers $$$k$$$ $$$(1 \le k \le 10)$$$, $$$n$$$ $$$(1 \le n \le 10^5)$$$, and $$$m$$$ $$$(1 \le m \le 10^5)$$$ — denoting the number of keys, the number of words Abu Adel knows, and the number of words in the logger, respectively.
The input will then contain $$$k$$$ lines, one for each digit from $$$0$$$ to $$$k-1$$$ respectively.
Each line will contain a string $$$s$$$ $$$(1 \leq |s| \leq 26)$$$, where $$$s$$$ is either a "#" (indicating that the key is not mapped to any lowercase English letter) or a string of distinct lowercase English letters representing the characters mapped to the current key.
Note: It is guaranteed that each of the 26 lowercase English letters is mapped to exactly one key.
The next $$$n$$$ lines each contain a string $$$w$$$ $$$(1 \le |w_i| \le 10^5)$$$ — where $$$w_i$$$ denotes the $$$i_{th}$$$ word that Abu Adel knows. It is guaranteed that all characters in $$$w_i$$$ are lowercase English letters only.
The next $$$m$$$ lines each contain a string $$$p$$$ $$$(1 \le |p_i| \le 10^5)$$$ — where $$$p_i$$$ denotes the $$$i_{th}$$$ pattern in the log file. It is guaranteed that $$$p$$$ consists only of digits from $$$0$$$ to $$$k-1$$$.
It is also guaranteed that the sum of $$$|w_i|$$$ across all words Abu Adel knows is less than $$$10^6$$$, and the sum of $$$|p_i|$$$ across all patterns is less than $$$10^6$$$.
Print $$$m$$$ integers, where the $$$i_{th}$$$ integer represents the number of words that match the $$$i_{th}$$$ pattern.
10 4 3abc#defghijklmnopqrs#tuvwxyzmoonhellohijalnop3444323343330
2 1 1
1 2 3abcdefghijklmnopqrstuvwxyzhellomoon000000000000
1 1 0
Abu Jawdat wants to conduct a population census for the residents of Haret Al-Dhabe3, So Abu Jawdat gathered his men from the police station and went to the houses to find out the names of the men and women in each household.
While collecting the names, he met Abu Hatem to ask about his daughters' names (Ya baaateeel shoooo). Abu Hatem responded, "The oldest one's name is mart el 3ageed Abo Shehab."
After Abu Jawdat recorded the names of the residents of Haret Al-Dhabe3, he wants to enter these names into the computer to be stored in the database owned by ElFrensawi (Ya baaateeel).
The problem is that the system only accepts names in English, so Abu Jawdat translated the names and used lowercase English letters, numbers, and the underscore _ symbol to represent the full name of each individual.
Abu Jawdat now needs to enter the translated names. To do this, he has a keyboard with all the English letters, numbers, and the underscore _ symbol.
Additionally, there is an "erase" button, which will delete the last character.
The program developed by the French for Abu Jawdat is very simple. It contains:
Abu Jawdat types the name in the text box and then presses save to store the name in the French database.
When the save button is pressed, the text box remains unchanged, and the name that was written stays without being cleared. Note that the "save" button is not a keyboard button.
There is a rule that after he finishes saving the names, he should erase the last name so the text box becomes empty, then he can close the program.
Abu Jawdat can enter the names in any order he wants because they will be arranged automatically in the database. Abu Jawdat is very lazy and wants to enter all the names with the fewest clicks on the keyboard.
Can you help Abu Jawdat by telling him what is the minimum number of clicks he needs to make to store all the names and close the program?
The first line will contain one integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — denotes is the population of Haret Al-Dhabe3.
For the next $$$n$$$ lines, the $$$i_{th}$$$ line will contain a string $$$s_i$$$, which represents the translation of the name of the $$$i_{th}$$$ resident.
Each character in $$$s_i$$$ will be a lowercase English letter, or a digit between '0' and '9' or the character underscore _ and the length of $$$s_i$$$ will not exceed 30.
Print the minimum number of keyboard clicks Abu Jawdat needs to make in order to save all the names.
5shareefehhameedehiftikarnawalmo6ee3ah
74
4abu_hatemabu_basheerabu_5a6erabu_3esam
52
43esamme3tazbasheer5a6er
46
2abcabd
8
The following image shows a better visualization of the first example
In the fourth sample:
He will save in the order $$$abc$$$, $$$abd$$$
The clicks are $$$[a , b , c , save , erase, d , save, erase, erase, erase]$$$
Anatidaephobia is the fear that a duck may be watching you.
M3taz is afraid of ducks and has never been on a lake trip because of it.
However, his friends want to surprise him with a lake trip, but they need to find a lake with no ducks so that M3taz can join them. Help M3taz friends plan a surprise lake trip by determining which lakes are suitable for him to visit.
You are given the number of ducks in each lake. For each lake. If a lake has no ducks, it is suitable for M3taz to visit. Otherwise, it is not suitable for him to visit.
Determine whether it is suitable for M3taz to visit the lake or not.
The first line of the input contains an integer $$$n$$$ $$$(1 \le n \le 10^4)$$$ — denotes the number of lakes.
For each lake you are given a single integer $$$x$$$ $$$(0 \le x \le 100)$$$ — denotes the number of ducks in the $$$i_{th}$$$ lake.
Print $$$n$$$ lines, each line print "YES" if M3taz can go to that lake, print "NO" otherwise.
You can output the answer in any case. For example, the strings "yEs", "yes", and "YES" will also be recognized as positive responses.
32077
NO YES NO
Mocha, a playful cat from Harat Al-Daba3, loved playing games. One day, he came across a famous cat named Basboos and wanted to challenge him to a game. However, he couldn't think of a suitable game.
Mocha and Basboos decided to play by each picking a random string. Mocha chose $$$s$$$, and Basboos chose $$$t$$$. The winner would be the one with the lexicographically smaller string.
Abu Bashir overheard their game and wanted to help Mocha win. He came up with an idea: he would generate a third string $$$k$$$ and insert it anywhere within $$$s$$$ and anywhere within $$$t$$$.
More formally, Abu Bashir wants to create two strings $$$s'$$$ and $$$t'$$$ such that $$$s' \lt t'$$$ by inserting $$$k$$$ somewhere into $$$s$$$ and somewhere into $$$t$$$, respectively.
Can you help Abu Bashir find a valid string $$$k$$$ that ensures Mocha's victory, or determine if it's impossible?
Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. $$$^{\text{∗}}$$$
$$$^{\text{∗}}$$$ We say that string $$$a$$$ is lexicographically smaller than string $$$b$$$ if and only if one of the following holds:
A formal definition is as follows: string $$$p$$$ is lexicographically smaller than string $$$q$$$ if there exists a position $$$i$$$ such that $$$p_i \lt q_i$$$, and for all $$$j \lt i$$$, $$$p_j = q_j$$$.
If no such $$$i$$$ exists, then $$$p$$$ is lexicographically smaller than $$$q$$$ if the length of $$$p$$$ is less than the length of $$$q$$$. For example, $$$abdc \lt abe$$$ and $$$abc \lt abcd$$$, where we write $$$p \lt q$$$ if $$$p$$$ is lexicographically smaller than $$$q$$$.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.
For each test case you are given two lines containing strings $$$s$$$ and $$$t$$$ respectively $$$(1 \le |s| , |t| \le 10^5)$$$ — $$$|s|$$$ denotes the length of $$$s$$$ and $$$|t|$$$ denotes the length of $$$t$$$.
The string is guaranteed to have only small letters without numbers.
It is guaranteed that the sum of lengths of all strings $$$s$$$ and $$$t$$$ in the input doesn't exceed $$$2\cdot10^5$$$.
For each test case if there is a valid solution print two lines, in the first line print the generated string $$$k$$$ ($$$1 \le |k| \le |s| + |t|$$$), and in the second line print two integers $$$i$$$ ($$$0 \le i \le |s|$$$) which indicates how many characters in string $$$s$$$ will be before string $$$k$$$ and $$$j$$$ ($$$0 \le j \le |t|$$$) which indicates how many characters in string $$$t$$$ will be before string $$$k$$$. If there are multiple solutions, print any of them.
Or say that it impossible by printing $$$-1$$$
In the second test case, the resulted strings are $$$s$$$ = "appl$$${\color{red}{entytaleggg}}$$$epie", $$$t$$$ = "mo$$${\color{red}{entytaleggg}}$$$onthemoon"
Moon had the worst breakup ever, again. His ex was way smarter than him, which devastated him. So, he needed advice from the one and only Apple, again. Apple decided to take Moon to Abu Shehab for help.
Moon said, "4 JAYYED."
Apple introduced Moon to Abu Shehab, and as Moon began to open up, Abu Shehab sighed and said, "moshkeltak kbeereh kteeeeer lek Moooooon"
Abu Shehab gave Moon a map of Haret Al-Dabe3. The map looks like a tree with $$$n$$$ nodes, where the nodes are numbered from $$$0$$$ to $$$n-1$$$.
A tree is a connected graph without cycles, where there is a unique path between any two nodes.
Abu Shehab told Moon that he should choose two nodes, $$$x$$$ and $$$y$$$, in the tree and walk along the path from $$$x$$$ to $$$y$$$. To forget his ex, he should choose the two nodes so that the $$$\operatorname{MEX}$$$ of the indices of the nodes on the path is as large as possible.
Can you help Moon solve this problem?
Note: The $$$\operatorname{MEX}$$$ (Minimum EXcluded value) of an array is the smallest non-negative integer that is not in the array. For example:
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. Each test case consists of two lines:
The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5 $$$), — denotes the number of nodes.
Then the input will contain $$$n-1$$$ lines, each line will contain two integers $$$u$$$ and $$$v$$$ $$$(0 \leq u \leq n - 1)$$$ $$$(0 \leq v \leq n - 1)$$$, which means that there is an undirected edge between nodes $$$u$$$ and $$$v$$$.
The sum of the values of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, print the maximum $$$\operatorname{MEX}$$$ of the set of nodes for a path in the tree.
340 10 20 340 11 22 360 44 20 14 34 5
3 4 3
Abu Shehab shekleen ma be7kee.
In the third example Moon should choose the path between nodes $$$1$$$ and $$$2$$$:
