Hanagasumii vs Ghaith_zakaria
A. Abu HatemCPC
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abu Hatem has a very famous coffee shop. Sometimes, they play games, and it becomes very competitive. Abu Hatem is also very keen on shabab el7ara; he always takes care of them and wishes them all the best. For that reason, he decided to teach shabab el7ara competitive programming so they can get jobs in the best companies.

Also, Abu Hatem wants to create competitive and fun events, so he decided to organize a programming contest called AbuHatemCPC.

Ma2moon beik is not just 3meel from frensawi; he also works in a big tech company as a recruiter. One of the things he was thinking about when he entered Haret AlDabe3 was finding good and skilled programmers for his company.

So he decided to come to AbuHatemCPC to view the contest and see how shabab el7ara performed, as well as to headhunt skilled and smart contestants.

Ma2moon beik arrived at the contest just after it ended, and he saw the final scoreboard but without the results of the submissions in the blind hour.

AbuHatemCPC had 13 problems, and its duration was (4 + 1) hours. In the first 4 hours, the submission results were public to all contestants, but in the last hour, only the team that made the submission could see its result (whether it was accepted or not).

When Ma2moon beik saw the scoreboard, he could see, for each team, the number of problems they solved before the blind hour and their time penalty. He could also see, for each team, the submissions they made in the blind hour as pending submissions.

When revealing the results, they would use the contest resolver to show whether each pending submission was accepted or not.

Now, each pending submission has two possibilities: to be accepted or not. If it is accepted, it will increase the number of solved problems for that team by 1 and increase the time penalty by some known amount.

The rank of each team is equal to $$$1$$$ plus the number of teams that solved a strictly greater number of problems or solved the same number of problems with a strictly lower time penalty. (If two teams solved the same number of problems with the same time penalty, they would have the same rank.)

Now, Ma2moon beik is wondering, for each team, considering all possible outcomes of the pending submissions, what is the highest and lowest rank this team can get. Can you help him?

Input

The first line will contain one integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$, which is the number of test cases.

For each test case:

The first line will contain one integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, which is the number of contestants.

Then, for each contestant, the input will contain two lines. For the $$$i_{th}$$$ contestant:

The first line will contain three integers $$$x_i$$$, the number of problems solved before the blind hour, $$$y_i$$$, the number of pending submissions in the blind hour, and $$$p_i$$$, the time penalty of the problems solved before the blind hour. It is guaranteed that $$$(0 \leq x_i + y_i \leq 13)$$$ and $$$(0 \leq p_i \leq 10^4)$$$. It is guaranteed that if the number of solved problems before blind hour ($$$x_i$$$) is $$$0$$$, the time penalty before blind hour ($$$p_i$$$) will also be $$$0$$$.

The second line will contain $$$y_i$$$ integers, the $$$j_{th}$$$ one denoted as $$$a_{i,j}$$$ $$$(240 \leq a_{i,j} \leq 500)$$$ , which represents the time penalty the contestant will receive if the result of that pending submission is accepted.

It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print $$$n$$$ lines. In the $$$i_{th}$$$ line, print the lowest and the highest rank the $$$i_{th}$$$ team could get.

Example
Input
1
5
3 2 100
240 250
1 5 500
250 260 270 280 290
5 0 849

0 0 0

0 1 0
240
Output
1 3
1 4
1 3
4 5
3 4
Note

First example final scoreboard before revealing results:

.

B. mart el 3ageed abo shehab
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

  • A text box.
  • A save button.

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?

Input

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.

Output

Print the minimum number of keyboard clicks Abu Jawdat needs to make in order to save all the names.

Examples
Input
5
shareefeh
hameedeh
iftikar
nawal
mo6ee3ah
Output
74
Input
4
abu_hatem
abu_basheer
abu_5a6er
abu_3esam
Output
52
Input
4
3esam
me3taz
basheer
5a6er
Output
46
Input
2
abc
abd
Output
8
Note

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]$$$

C. 5ayef men el ba6 lek M3tazzz?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

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.

Example
Input
3
2
0
77
Output
NO
YES
NO
Note

D. Moshkeltak kbeereh kteeeeer lek Moooooon
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $$$\operatorname{MEX}$$$ of $$$[1, 2, 3]$$$ is $$$0$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 2]$$$ is $$$3$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 3]$$$ is $$$2$$$
Input

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$$$.

Output

For each test case, print the maximum $$$\operatorname{MEX}$$$ of the set of nodes for a path in the tree.

Example
Input
3
4
0 1
0 2
0 3
4
0 1
1 2
2 3
6
0 4
4 2
0 1
4 3
4 5
Output
3
4
3
Note

Abu Shehab shekleen ma be7kee.

In the third example Moon should choose the path between nodes $$$1$$$ and $$$2$$$:

E. Abu Adel's Nokia 3311
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

Print $$$m$$$ integers, where the $$$i_{th}$$$ integer represents the number of words that match the $$$i_{th}$$$ pattern.

Examples
Input
10 4 3
abc
#
defg
hijklm
nop
qrs
#
tuv
wxy
z
moon
hello
hija
lnop
3444
32334
3330
Output
2
1
1
Input
1 2 3
abcdefghijklmnopqrstuvwxyz
hello
moon
00000
0000
000
Output
1
1
0
Note

F. talle3 el string lak ab bashiiiir
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$ is a prefix of $$$b$$$, but $$$a \neq b$$$.
  • in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

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$$$.

Input

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$$$.

Output

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$$$

Note

In the second test case, the resulted strings are $$$s$$$ = "appl$$${\color{red}{entytaleggg}}$$$epie", $$$t$$$ = "mo$$${\color{red}{entytaleggg}}$$$onthemoon"