The psychologist Arnon, in his researches in IME, developed the theory of the Arnon-Degree of Separation.
According to this theory, it's necessary at most $$$k$$$ friendship bonds to connect any two people in the world. But for his theory to impress people, especially his friends De Castro and Caio, he needs to discover $$$k$$$.
Since he is too busy going out with his girlfriend, he asks you to discover this value. He will give to you a sample test with $$$n$$$ people and $$$m$$$ friendship bonds and you have to answer the minimum integer $$$k$$$ such that the theory will be valid.
The first line contains two integers, $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \times 10^3, 0 \le m \le 2 \times 10^3$$$) — the number of people and the number of friendship bonds, respectively.
The next $$$m$$$ lines contains, each, two integers, $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) — indicating that $$$a$$$ and $$$b$$$ are friends.
Print "=]" (without quotes) followed by an integer indicating the value of $$$k$$$.
In case it's not possible to reach some of the $$$n$$$ people, you should print "=[" (without quotes), instead.
5 4 1 2 2 3 3 4 4 5
=] 4
7 7 1 2 3 6 2 4 3 5 2 5 2 3 2 7
=] 3
Like happens every year, the students from the first year of IME (Institute of Meticulous Edifices) are in the military training camp and one of the activities is to cross a river.
Normal students would cross the river swimming, but not the IME students! Each student's squad will have to build one bridge from one riverside to the other, but there's a catch, on each riverside there are areas reserved for each squad and the squads can only build a bridge starting and ending on areas reserved to that squad. Also the bridges are very weak, so they can't cross each other, including on riversides.
Before starting the activity, Lieutenant Lacoste asks for the Sheriff Sereno what's the maximum number of bridges that can be built, so he can divide the tasks equally.
Sheriff Sereno is too worried in maintaining the marking tapes untouchable to answer this question quickly, so he asks you (who was occasionally passing by) to calculate the answer.
The first line of input contains two lowercase English strings, $$$a$$$ and $$$b$$$ ($$$1 \le |a|, |b| \le 10^3$$$) — the areas reserved in each riverside. The $$$i$$$-th letter from string $$$a$$$ indicates that the area $$$i$$$ belongs to squad $$$a_i$$$, same goes for $$$b$$$.
Print the maximum number of bridges that can be built.
abacaba aba
3
aadodbcecoeo dcceoafas
5
Navarro, the main coach of the IME++ students, wants to choose a team for a contest, but the team must obey certain specifications.
Knowing that each student has a certain programming skill and that a team consists of at least $$$1$$$ student, Navarro wants the team to have a skill value (the sum of the team's skill) of at least $$$x$$$ and the difference between the best and the worst skill of the team should be at most $$$d$$$.
Navarro is too busy helping Caio to go well in contests and asks you to find the number of teams that can be formed under the specifications above.
Two teams are considered different if at least one of the members differ.
First line contains three integers $$$n$$$ ($$$1 \le n \le 15$$$), $$$x$$$ ($$$0 \le x \le 10^9 $$$) and $$$d$$$ ($$$0 \le d \le 10^9$$$) — the number of students, the minimum value of skill and the maximum difference between the best and worst skills.
Second line contains $$$n$$$ space-separated integers $$$s_i$$$, where $$$s_i$$$ ($$$0 \le s_i \le 10^9$$$) indicates the skill of the $$$i$$$-th student.
Print the number of teams that can be formed under Navarro's specifications.
1 7 50 8
1
5 17 5 10 34 23 57 64
4
Everyone knows Tuesday is Donimo's Day! Probably not the best pizza around, but people from the International Math-addicted Engineers (IME) like the discounts from Tuesday so much that they are willing to improve their method of dividing the pizza slices.
This Tuesday a total of $$$n$$$ people ordered $$$2 \times n$$$ pizza slices from Donimo's. The slices are not cut exactly equal and every person will eat 2 slices each. They want the division to be the most fair as possible.
The most fair division is the one that the difference between the amounts of pizza eaten by the person that eaten the most and the person that eaten the least is minimum possible.
Your task is to calculate the most fair division and print the difference between the amounts pizza eaten by the person that ate the most and the person that ate the least.
The first line contains one integer, $$$n$$$ ($$$2 \le n \le 10^4)$$$ — the number of people ordering pizza.
The second line contains $$$2 \times n$$$ integers, $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the size of each slice.
Print the minimum difference between the amounts pizza eaten by the person that eaten the most and the person that ate the least.
2 1 4 3 2
0
4 5 1 1 4 3 2 11 3
6
Cadet Yu Yi Hakusho got caught, by Captain Leitor, leaning against the wall for the $$$4^{th}$$$ time. Furious, Captain Leitor ordered Yu Yi to write an essay about why he should not lean against the wall and, as he was not in a good mood, he also said that no word with four or more letters should be repeated.
Desperate, Yu Yi wrote many lines, trying not to repeat any word but, when he finished writing, he was not so sure about it so he wrote all words on his computer. As he doesn't know how to see which words are repeated, he asked you to help him.
Write a program that, given a list of words, tells which words Yi Yu should erase.
The first line contains one integer, $$$n$$$ ($$$1 \le n \le 8 \times 10^6$$$) — the number of words that Yu Yi wrote.
The next $$$n$$$ lines contains, each, one string, $$$s_i$$$ — the words Yu Yi wrote.
The words contains only lowercase English letters. The sum of the length of all words is not greater than $$$8 \times 10^6$$$.
In the first line print the number of repeated words.
In the next lines, print all repeated words in the same order they repeat, separated by spaces.
If there are no repeated words, print "SAFO" (without quotes).
6 not clean bad posture clean enough
1 clean
8 not clean enough bad posture clean enough enough
3 clean enough enough
At IME++, students learn multiple algorithms and data structures and usually participate in contests. Some contests are individual, others are in trios and some, rare ones, are in groups of any size.
In $$$2019$$$ one of the rare any-group-size contests appeared, so every student of IME++ decided to participate. Although the contest have no size limits, some students don't work so well with others, so they decided that each student will start in it's own team and then the teams will be joining others.
You are responsible to verify if the students are happy with the teams or not, so you know ahead of time which student pairs don't work very well together and, while the teams are getting decided, you want to know if a pair of students are in the same team or not.
IME++ has $$$n$$$ students, you know the first name of each student (the size of the names are at most 10 English letters with the first letter uppercase and the rest lowercase, all names are distinct), also there are $$$q$$$ queries of two types:
The first line of input contains two integers, $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$) — the number of students at IME++ and the number of queries, respectively.
The next $$$n$$$ lines contains, each, one string, $$$s_i$$$ ($$$2 \le |s_i| \le 10$$$) — the name of the $$$i$$$-th student. The names are in English alphabet with first letter uppercase and rest lowercase. All names are distinct.
The next $$$q$$$ lines contains, each, one integer and two strings, separated with spaces, $$$t_i$$$, $$$s_x$$$ and $$$s_y$$$ ($$$1 \le t_i \le 2$$$, $$$s_x \ne s_y$$$) — the type of the $$$i$$$-th query and the names of the students of the $$$i$$$-th query. It's guaranteed that $$$s_x$$$ and $$$s_y$$$ are names of students. If $$$t_i$$$ equals $$$1$$$ and the students $$$s_x$$$ and $$$s_y$$$ are already on the same group, nothing changes.
It's guaranteed that there will be at least one query of type $$$2$$$.
For each query of type $$$2$$$ you must print "yes" or "no" (without quotes), meaning if the given students are in the same group or not, respectively.
6 13 Navarro Arnon Matheus Xavier Rebeca Naum 1 Naum Rebeca 2 Rebeca Naum 1 Matheus Xavier 1 Navarro Arnon 2 Matheus Navarro 2 Rebeca Matheus 1 Navarro Matheus 2 Xavier Arnon 2 Xavier Rebeca 1 Rebeca Arnon 2 Naum Rebeca 2 Naum Matheus 2 Naum Xavier
yes no no yes no yes yes yes
6 8 Sergio Yu Mateus Cesar Gustavo Caio 1 Sergio Mateus 1 Cesar Yu 1 Cesar Gustavo 2 Cesar Sergio 1 Caio Mateus 1 Gustavo Yu 2 Caio Sergio 2 Gustavo Sergio
no yes no
The semester is ending and Naum decides to establish the grade concept of the IME++ members. The concept is formed by several grades given by him to the members in moments of pride or disappointment during the semester, which can be represented as a sequence of grades, numbered from $$$1$$$ to $$$n$$$.
The grade concept could be just the sum of all the grades given by him, but Naum decided to complicate a little bit, creating the following criteria: the grade concept will be the sum of the grades from range $$$l$$$ to $$$r$$$, minus the value of the minimum and maximum value in this range (for normalization, of course). More formally, $$$f = sum(l, r) - max(l, r) - min(l, r)$$$, where $$$f$$$ is the grade concept, $$$sum(l, r)$$$, $$$max(l, r)$$$ and $$$min(l, r)$$$ is the sum of all grades, maximum grade and minimum grade, from $$$l$$$ to $$$r$$$, inclusive.
Besides that, Naum decides to change the grades of some members, because he thought members like Navarro deserved a better grade concept, while others like de Castro deserved a worst grade concept.
Naum is too busy trying to fix bugs from Bing and he asks you to create a program that can help him calculate the grade concept. He will give you a sequence of $$$n$$$ grades and $$$q$$$ queries of two types:
The first line contains two integers $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — the number of grades and the number of queries, respectively.
The next line contains $$$n$$$ space-separated integers, $$$grade_i$$$ ($$$0 \le grade_i \le 10$$$) — the value of the $$$i$$$-th grade.
The next $$$q$$$ lines contains, each, one integer, $$$t$$$ ($$$1 \le t \le 2$$$), indicating the type of the $$$i$$$-th query, and two other integers, described below, depending on the query type.
If $$$t_i$$$ equals $$$1$$$, the integers are $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l \le r \le n$$$) — the range considered in the grade concept.
If $$$t_i$$$ equals $$$2$$$, the integers are $$$i$$$ and $$$v$$$ ($$$0 \le value \le 10$$$), — the grade position in the sequence and it's new value, respectively.
It's guaranteed that at least one query is of type $$$1$$$.
For each query of type $$$1$$$ print it's grade concept.
1 3 10 1 1 1 2 1 8 1 1 1
-10 -8
3 3 9 6 5 1 1 3 2 3 7 1 1 3
6 7
In a very distant future, in the last year of graduation at IME, the VFs are coming for César and once again he got low grades. The dream of needing no more than $$$4$$$ to pass the semester is far away, but there is hope, at least for the Encryption discipline.
The professor gave a list of exercises (to raise the VE grade), but this time he got too wicked. To solve the list, César has to decrypt $$$q$$$ messages. The algorithm is quite simple, but there is a hard math part. For every message, César has to find some integer $$$x$$$ such that $$$n^x \equiv 1 \pmod m$$$, where $$$m$$$ and $$$n$$$ are parameters already calculated from the algorithm.
Finishing these calculations is all he need to hand the list. As César needs more than $$$4$$$ on all other disciplines, he doesn't have time to finish it, so you will have to help him.
The first line of input contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of messages to decrypt.
The next $$$q$$$ lines contains, each, two integers, $$${n_i}$$$ and $$${m_i}$$$ ($$$1 \le n_i \lt m_i \le 10^6$$$) — the parameters $$${n_i}$$$ and $$${m_i}$$$ for the $$$i$$$-th query.
For each $$$n_i$$$ and $$$m_i$$$ from the input, print an integer $$$x_i$$$ ($$$0 \le x_i \le 10^6$$$) such that $$${n_i}^{x_i} \equiv 1 \pmod{m_i}$$$.
If it doesn't exists, print $$$-1$$$.
1 3 5
4
1 2 4
-1