Plus
Pin


Problem description Progress
ID 21822. HASH
Темы: hash   

Programmer Vasya was unlucky - instead of a vacation, he was sent on a business trip to a scientific conference. "We need to increase the level of knowledge," said the boss, "An important conference on cryptography is being held in France - and there they encrypted back in the time of Richelieu and cracked other people's ciphers back in the time of Vieta."
Vasya quickly found out that he had already seen all the Louvre paintings somewhere, the sight of the Eiffel Tower became boring to him even before the mouse wiped it off the rug, and we make such glass pyramids for all sorts of kiosks and dubious eateries. In a word, there was simply nothing to see in Paris, there was nowhere to fish, so Vasya had to attend reports at the conference.
One of the speakers, once again trying to unravel Bacon's ciphers, put forward a hypothesis that the key to Bacon's mysteries can be found by analyzing all possible substrings of Bacon's works. "But there are too many of them!" Vasya was surprised aloud. "No, not so much!" - shouted the speaker, - "Calculate, and you will see for yourself!"
The same evening, Vasya found the complete works of Bacon on the Internet. He wrote a program that converted the texts into one long line, removing all spaces and punctuation marks from the texts. And now Vasya is very puzzled - how to count the number of different substrings of this string? 

Input
The input contains a non-empty string received by Vasya. The string consists only of lowercase Latin characters. Its length does not exceed 2000 characters. 

Output
Print the number of different substrings of this string.

 

Examples
# Input Output
1 aaba 8

ID 38255. Beautiful numbers
Темы: hash   

In one small country, it was allowed to open offshore companies, and entrepreneurs immediately rushed there with the desire to open their own company in it.

Since all firms are modern and keep up with the times, they need to contact customers and business partners, which means they need a phone number.


Thus, each letter corresponds to a certain number, and instead of a telephone number, it is enough to know the word whose letters correspond to the digits of the number.

Every company wants their phone number to be easy to remember. If the company name typed on the phone matches the company phone number, the number is very easy to remember and no customer will ever forget it.

Since there are so many companies, not all companies may be able to get a convenient number. Write a program that will determine the largest number of firms that can get such a number.

Input
The first line contains an integer N — number of new firms (1 ≤ N ≤ 103).

In the next N lines enter the names of firms. The name of each company consists of seven lowercase Latin letters. It is guaranteed that the names of all firms are different.

Imprint
Print one number — the maximum number of firms that can get a convenient number.

Examples
# Input Output
1 4
lacoste
hyundai
renault
peugeot
4
2 3
aaaaaaa
bbbbbbb
ccccccc
1

ID 38374. magic mushrooms
Темы: hash   

There is a Large Corporation of Little Fairies on the planet Ruuk. One of the activities that her employees have been doing for centuries is planting beds with magic mushrooms. Every day, starting from the very first day of the existence of this corporation, the fairies create one new patch of mushrooms. After that, from the new bed, for two days, you can collect spores that reproduce these mushrooms, and then the bed will supply only the product itself — mushrooms.

Thus, if we denote the number of mushrooms planted in the garden created on the day number i as ci , then it will be calculated according to the formula ci = ci - 1 + ci - 2< /sub>. So, on the first and second days, one mushroom was planted, on the third — two, the fourth — three, in the fifth — five and so on.

Magic mushrooms are the most valuable souvenir a traveler can bring back from the planet Ruuk. Therefore, the first thing any visitor does is to search for a bed with magic mushrooms. However, lately there have been increasing reports of fake magic mushrooms. Careful investigation revealed that this is the result of the Little Big Fairy Corporation, which plant beds with mushrooms that are indistinguishable in appearance, but nowhere near as valuable as magical ones. Moreover, when creating another garden bed, these fairies plant there such a number of mushrooms that their rivals have never planted and cannot plant.

It would seem that after finding out this fact, it became easy to distinguish magic beds from fake ones. But both corporations have existed for a long time, the number of beds and mushrooms on them has long exceeded all reasonable limits. You have been asked to write a program that tells you, by the number of mushrooms in a garden, whether the garden is magical.

Input

The first line of the input file contains a single number N (1 ≤ N ≤ 1000000) — the number of studied beds. The following n lines contain one integer each ai — the number of mushrooms in the studied beds. The size of the input file does not exceed 1 MB.

Imprint

For each number given in the input file, print "Yes" if the garden with that many mushrooms is magical, and "No" — if not. Separate your answers with line breaks.

Examples
# Input Output
1 8
1
2
3
4
5
6
7
8
Yes
Yes
Yes

Yes


Yes

ID 38511. Journey along the line
Темы: Segment tree, RSQ, RMQ    sqrt decomposition    hash    Suffix array    Dynamic programming    hash   

Let's say that the sequence of strings t1 , ..., tk is a journey of length k if for all i > 1 ti< /sub> is a substring of ti - 1 of strictly less length. For example, { ab , b } is a journey, and { ab , c } or { a , a } — no.

Define a string traversal s as a traversal t1 , ..., tk , all of whose strings can be nested in s such that there are (possibly empty) strings u1 , ..., uk + 1 such that s = u1t1 u2 t2 ... uk tk uk +&thinsp ;1 . For example, { ab , b } is a string travel for abb , but not for bab , since the corresponding substrings are from right to left.

Let's call the length of the journey the number of lines of which it consists. Determine the maximum possible travel length along the given string s .

Input
The first line contains an integer n ( 1 ≤ n ≤ 500 000 ) — length of string s .

The second line contains the string s , consisting of n lowercase English letters.

Imprint
Print one number — the longest travel length in string s .

Note
In the first example, the longest string traversal is { abcd , bc , c } .

In the second example, { bb , b } would be appropriate.

Examples
# Input Output
1 7
abcdbcc
3
2 4
bbcb
2

ID 38511. Journey along the line
Темы: Segment tree, RSQ, RMQ    sqrt decomposition    hash    Suffix array    Dynamic programming    hash   

Let's say that the sequence of strings t1 , ..., tk is a journey of length k if for all i > 1 ti< /sub> is a substring of ti - 1 of strictly less length. For example, { ab , b } is a journey, and { ab , c } or { a , a } — no.

Define a string traversal s as a traversal t1 , ..., tk , all of whose strings can be nested in s such that there are (possibly empty) strings u1 , ..., uk + 1 such that s = u1t1 u2 t2 ... uk tk uk +&thinsp ;1 . For example, { ab , b } is a string travel for abb , but not for bab , since the corresponding substrings are from right to left.

Let's call the length of the journey the number of lines of which it consists. Determine the maximum possible travel length along the given string s .

Input
The first line contains an integer n ( 1 ≤ n ≤ 500 000 ) — length of string s .

The second line contains the string s , consisting of n lowercase English letters.

Imprint
Print one number — the longest travel length in string s .

Note
In the first example, the longest string traversal is { abcd , bc , c } .

In the second example, { bb , b } would be appropriate.

Examples
# Input Output
1 7
abcdbcc
3
2 4
bbcb
2

ID 39669. double string hash
Темы: hash    Formula derivation   

You are given t queries, in each of which you are given a string s consisting of lowercase Latin letters, a number p and a number mod.
For each query, compute a polynomial hash modulo base p of the string that is the string s, where each letter is duplicated. That is, if s = "isaac", then you need to calculate the hash from the string "iissaaaacc".

Input:
The first line contains the number t - the number of requests.
Then there are t lines, each containing space-separated s (1 <= |s| <= 20), p (1 <= p <= 105) and mod ( 1 <= mod <= 108).

Output:
Print the responses to the queries, each on a separate line.

Example:
 

Input Output
2
isaac 12345 87654321
newton 54321 12345678
8829000
9632318

ID 39670. Strange dream of Constantine
Темы: hash    Bor    Trees    Trees   

Once Konstantin, having participated in the next, already the 13th international Olympiad, was returning home by train. He, as always, sat and thought about the meaning of life, simultaneously solving programming problems. After some time, Konstantin dozed off, but the trouble is, in order to wake up, he must solve the problem that has popped up in his head, which haunts him!

This time, Konstantin dreamed of a tree that initially consisted of only one vertex with number 1. In the problem he set, new vertices were gradually added to the tree. In the i-th second, a vertex with the number i+1 was added to the tree, which was suspended as a son from the vertex pi, and on the edge between the vertices i+1 and pi the letter ci was written.

Each path from the root of the tree to the vertex v corresponds to a certain string obtained by writing out the symbols written on the edges of the current path in the order from the root to the vertex v. Konstantin faced a difficult task at first glance - after each addition of a new vertex, count the number of unique strings starting at the root of the tree (vertex number 1) and ending at some other vertex. 

In his dream, Konstantin is not a genius at all, so he himself cannot solve this problem. Help Konstantin solve the problem and wake up.

Input:
The first line contains the number n - the number of requests to add a new node to the tree (1 <= n <= 300000).
The next n lines describe requests for adding vertices. The i-th query is described by the parameters pi (1 <= pi <= i) and ci, which mean that the added the vertex with number i+1 is suspended from the vertex with number pi as a child, and the symbol ci is written on the resulting edge - a lowercase letter of the Latin alphabet.

Output:
Print n lines. On the i-th line print the answer to Konstantin's problem after adding the i+1-th vertex.

Examples:
 

Input Output
2
1 b
2p
1
2
3
1 o
1 o
2 j
1
1
2

ID 39671. Substrings in a string
Темы: hash    Prefix sums(minimums, ...)   

Given a string S = s1s2...sn and a set of queries like (l1, r 1, l2, r2). For each query, it is required to answer whether the substrings sl1...sr1 and sl2...sr2 are equal .


Input:
The first line contains the string S (1 <= |S| <= 105) consisting of lowercase Latin letters. 
The second line contains a natural number q (1 <= q <= 105) - the number of requests.
The next q lines contain 4 natural numbers each - l1, r1, l2, r2 ( 1 <= l1 <= r1 <= |S|, 1 <=l2 <= r< sub>2 <= |S|).

Output:
For each query, print '+' if the substrings are equal, and '-' otherwise.

Examples:
 

Input Output
abacaba
4
1 1 7 7
1 3 5 7
3 4 4 5
1 7 1 7
++-+

ID 39672. Tom Sawyer and the word on the fence
Темы: hash    Greedy Algorithm    Prefix sums(minimums, ...)   

While painting the fence, Tom Sawyer wrote the word s on it. However, he then decided that palindrome words looked prettier.
Now he wants to add another word g to the given word s on the right so that the resulting word sg is a palindrome. However, in order to save paint, the length g should be as short as possible.
Help Tom Sawyer identify the word g.

Input:
The first line contains the word s (1 <= |s| <= 200000) consisting of lowercase Latin letters.

Output:
Print the minimum possible length of the word g that needs to be completed so that the word sg on the fence becomes a palindrome. If you don't need to add anything, then print '-'.

Examples:
 

Input Output
abc ba
a -

ID 39673. Reading aloud
Темы: hash    Prefix sums(minimums, ...)    Binary search    Binary search by answer   

Tom Sawyer and Huckleberry Finn read a newspaper clipping aloud together. But it so happened that Tom Sawyer began to read from the i-th character, and Huckleberry Finn from the j-th. 
How many letters can they read before they find they started from different places, or until they both read to the end?

Input:
The first line contains the string S (1 <= |S| <= 105), consisting of lowercase Latin letters - an inscription from a newspaper clipping.
The next line contains a natural number q - the number of requests.
The next q lines contain two natural numbers i and j each - the positions from which Tom Sawyer and Huckleberry Finn start reading, respectively.

Output:
Print q lines, each of which should contain one integer - the number of characters that match when reading substrings starting with the i-th and j-th characters.

Examples:
 

Input Output
abacaba
4
15
3 5
4 2
26
3
1
0
2

ID 39674. Huckleberry Finn and two strings
Темы: hash    Prefix sums(minimums, ...)    Bust   

Huckleberry Finn has two strings s and t of the same length n.
Huckleberry Finn likes strings to have the same prefixes (beginnings), so he can swap two characters in string s to make the common prefix of strings s and t larger.
However, this trick is rather tedious, so Huckleberry Finn will either not do it at all, or will do it exactly once.

Help Huckleberry Finn determine the longest common prefix length of strings s and t that he can get.


Input:
The first line contains a natural number n (1 <= n <= 200000) - the length of strings s and t
The second line contains a string s, consisting of lowercase Latin letters.
The third line contains a string t consisting of lowercase Latin letters.

Output:
Print one natural number - the maximum length of the common prefix s and t, which can be obtained by exchanging two characters in the string s at most once.

Examples:
 

Input Output
3
wai
add
1
5
qdyid
xreac
0

ID 39675. cultural contact
Темы: hash    Prefix sums(minimums, ...)    Bust   

At the beginning of the 18th century, a group of European explorers arrived on an island inhabited by a group of tribes that had never come into contact with representatives of European civilization.

To successfully establish contacts with the natives, the leader of the group plans to give a gift to the leader of each tribe he meets. To this end, he brought a long chain of glass, similar to precious stones. 
Let's represent the string as a string s, consisting of small letters of the English alphabet, where each letter means the type of piece of glass at the corresponding position. 
The researchers are going to cut the chain into some fragments, and then hand over exactly one fragment to the leader of each tribe encountered by the group. The research leader decided to split the chain into fragments according to the following rules:

  • In order not to spend a lot of time on cutting, each fragment should be a group of adjacent pieces of glass in the chain, that is, a substring of the string s.
  • All pieces of glass must be used, that is, each piece of glass must be included in exactly one fragment.
  • Because the researchers don't know how the aborigines will value certain types of glass, they want each chief to get the same set of glass without regard to order. In other words, for any type of glass, the number of glass of this type must be the same in each of the fragments.
  • Researchers don't know how many tribes live on the island, so the number of prepared fragments should be as large as possible.

Help the manager determine the maximum number of fragments that can be obtained.

Input:
The first line contains the string s (1 <= |s| <= 5000000).

Output:
Print a single number - the maximum possible number of fragments into which the researchers can cut the chain they have without violating any of the conditions formulated by the group leader.

Examples:
 
Input Output
abbabbbab 3
aabb 1

Explanations:
In the first example, researchers can break the chain 'abbabbbab' fragments 'abb', 'abb', 'bab', then the leader of each tribe they meet will get one glass of type 'a' and two pieces of 'b'.

In the second example, the string cannot be divided into more than one fragment of the chain, observing all the conditions.

ID 39676. Bunkers
Темы: hash    Trees   

Petya and Vasya enthusiastically play spies. Today they are planning where they will be 
located their secret bunkers and headquarters. 

So far, Petya and Vasya have decided that they will need exactly n bunkers, which will be numbered from 1 to n for secrecy. 
Some of them will be connected by two-way tunnels, and for reliability and secrecy, the tunnels will be accessible from any bunker to any one way.
Petya and Vasya even decided which of the bunkers will be connected by tunnels, but they cannot choose which one will be the headquarters. 
The boys want to choose it and divide the remaining bunkers among themselves so that they get an equal number of bunkers. Exactly two tunnels lead to the headquarters: one from the bunker belonging to Vasya, the other from the bunker belonging to Petya. 
                                                                                   
Tired Petya went to his house, and in the morning Vasya showed him a plan on which the bunkers were marked with dots and the tunnels with segments. 
In addition, Vasya chose the headquarters in such a way that the plan he drew was symmetrical with respect to a straight line passing through the point that corresponded to the headquarters.
 
Although Petya almost immediately showed Vasya that he had made a mistake and did not draw half of the bunkers, he wondered if it was possible to choose a headquarters and draw such a symmetrical plan.

Input:
The first line of the input file contains a single integer n (1 <= n <= 105) - the number of bins. 
The next n - 1 lines contain two integers ui and vi (1 <= ui, vi <= n, ui ≠ vi) - numbers of bunkers connected by the i-th tunnel. 
It is guaranteed that there is only one path between any two bunkers.

Output:
In the output file print "YES" if it is possible to choose a headquarters and draw such a plan, or "NO" if that's not possible.

Examples:
 

Input Output
2
1 2
NO
3
1 2
2 3
YES