hash

ID 21822. HASH

Examples

ID 38255. Beautiful numbers

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 ≤ 10³).

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

ID 38374. magic mushrooms

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 c_i , then it will be calculated according to the formula c_i = c_i - 1 + c_{i - 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 a_i — 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

ID 38511. Journey along the line

Let's say that the sequence of strings t₁ , ..., t_k is a journey of length k if for all i > 1 t<sub>i< /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.</sub>

Examples

ID 38511. Journey along the line

Let's say that the sequence of strings t₁ , ..., t_k is a journey of length k if for all i > 1 t<sub>i< /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.</sub>

Examples

ID 39669. double string hash

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 <= 10⁵) and mod ( 1 <= mod <= 10⁸).

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

Example:
 

ID 39670. Strange dream of Constantine

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 p_i, and on the edge between the vertices i+1 and p_i the letter c_{i 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 p_i (1 <= p_i <= i) and c_i, which mean that the added the vertex with number i+1 is suspended from the vertex with number p_i as a child, and the symbol c_i 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:
 

ID 39671. Substrings in a string

Given a string S = s₁s₂...s_n and a set of queries like (l₁, r ₁, l₂, r₂). For each query, it is required to answer whether the substrings s_l1...s_r1 and s_l2...s_{r2 are equal} .


Input:
The first line contains the string S (1 <= |S| <= 10⁵) consisting of lowercase Latin letters. 
The second line contains a natural number q (1 <= q <= 10⁵) - the number of requests.
The next q lines contain 4 natural numbers each - l₁, r₁, l₂, r₂ ( 1 <= l₁ <= r₁ <= |S|, 1 <=l₂ <= r< sub>2 <= |S|).

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

Examples:
 

ID 39672. Tom Sawyer and the word on the fence

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:
 

ID 39673. Reading aloud

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| <= 10⁵), 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:
 

ID 39674. Huckleberry Finn and two strings

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:
 

ID 39675. cultural contact

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.

ID 39676. Bunkers

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 <= 10⁵) - the number of bins. 
The next n - 1 lines contain two integers u_i and v_i (1 <= u_i, v_i <= n, u_i ≠ v_i) - 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: