Description

Ugandan Knuckles keeps finding his queen. However, he lost his way. He decides to meditate and read some books. In Knuckles' religion, there are two kinds of string: "good string" and "bad string".

---

A string of length n is good if and only if no letter appears strictly more than n/2 times. For example " aabb ", " ababab " are good and " aab ", " abaab " are bad. 

Knuckles wants to find the substring in a string S.

For example,

for the string S = " aaabbbb ", the good substring includes " aaabbb ", " aabb ", " ab ".

Now you need to help Knuckles find the minimum length of the good substring in the given string S. It's guarantee that there will be at most one answer in each testcase.

Input

The input contains an integer n and a string S(only contains a~z).

n is the length of S.( 1<= n <= 10⁶ ).

There may be many test cases in each test, but it won't exceed 10 test cases in each test. The input ends with EOF.

Output

The output contains two lines. First line prints "YES" if there's an answer; otherwise, prints "NO".

The second line prints the answer of the minimum length of the good substring if there's an answer; otherwise, prints nothing.

(remember to print '\n' at the end of each line. If the second line has no answer, prints nothing )

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas wants to eat watermelon. But the watermelons are stored in a cylindrical(圓柱狀) box.

---

He has n watermelons and each one has a specific index denote as a_i.

Osas wants to eat a watermelon indexed a_i.

But if the watermelon indexed a_i is not on the top,

he needs to eat all watermelon above the watermelon indexed a_i.

Osas also has a list which is the order of watermelons he wants to eat which denoted as b_i.

The length of the list is also n and all b_i are distinct.

Please help him calculate that each time he wants to eat a watermelon, how many watermelons he needs to eat at same time?

 

For example ：

if the index of watermelon from top to bottom is: 5, 3, 2, 1, 4. And the list Osas has is: 2, 3, 4, 5, 1.

First time Osas will eat 3 watermelons(5,3,2).

Second time because the watermelons that indexed 3 is already been eaten, Osas eat 0 watermelon . So on and so forth.

In this example, you need to output: 3 0 2 0 0.

 

 

Input

input contains three lines.

First line contains n the number of watermelons.( 1 <= n <= 2*10⁵ )

Second line contains n integer a₁ ~ a_n which denote as the index of watermelons from top to bottom .( 1 <= a_i <= n )

 

Third line contains n integer b₁ ~ b_n which denote as the order of watermelons  that Osas' wants to eat.( 1 <= b_i <= n )

 

Output

output contains one line.

output n integer means the number of watermelons that each time Osas eat. Separate each number by a blank but don't print the blank after the last number.

remember to print \n at the end of output.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Johnny is a three years old kid. He likes to eat sugar. One day, he sneaked into the kitchen in order to grab some sugar to eat. Unfortunately, his papa catched him.

His papa called him: " Johnny, Johnny! "

Johnny replied: " Yes, papa. "

papa then asked: " Eating sugar? "

Johnny lied: " No, papa. "

At that moment, Johnny began to think that what's defintion of string equivalent?

---

Johnny thinks that string a and string b is equivalent if a and b are the same or string a and string b can be devided into two same size part: a₁, a₂, b₁, b₂ and the following rules fulfill：

(  ( a1 == b1 ) && ( a2 == b2 ) )  or  ( ( a1 == b2 ) && ( a2 == b1 ) )

In above sentence, "==" means whether a and b are the same or string a and string b can be devided into two same size part: a₁, a₂, b₁, b₂ and the following rules fulfill: (  ( a1 == b1 ) && ( a2 == b2 ) )  or  ( ( a1 == b2 ) && ( a2 == b1 ) ). You can consider this equal definition as a recursion.

For example: 

a = " papa ", b = " apap ", we need to check if " pa " equals " ap " in Johnny ' s rule.

Therefore, we divide " pa " into "p" and "a", and divide "ap" into "a" and "p". 

Then, because "p" == "p" && " a " == "a", we know that "pa" == "ap".

Hence, we can conclude that " papa " equals " apap ".

 

Note that we can't divide a string if the length of the string is an odd number.

Help Johnny find out whether the two string are the same. If you help him, he will give you some sugar.

 

 

 

 

Input

input contains two lines.

First line is the string a. 

Second line is the string b. 

the length of the two string are the same and the length is from 1~10⁵ ( 1 <= length <= 10⁵ )

 

Output

output contains one line.

print "YES" if two string is equal in Johnny's rule,

print "NO" otherwise.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

PaPa suspected that Johnny ate the sugar, yet Johnny said he hadn't eaten it.

Therefore, PaPa asked: " Telling lies? "

Johnny replied: " No PaPa. "

PaPa then demanded: " Open your mouth! "

Johnny laughed embarrassedly: " Ha Ha Ha!!! "

PaPa is so furious with Johnny telling lies, so he punished Johnny to do some math.

---

PaPa gave Johnny n numbers a₁ ~ a_n and a number k.

PaPa asked Johnny to calculate how many ways he could pick some numbers from a₁ to a_n in order to make their sum equal to k?

For example:

Given n = 5 and numbers are { 1,2,3,3,3 }, and k = 3, the answer is 4.

(Note that although there are three identical "3", we still consider them as different indentities.) { (1, 2), (3), (3), (3) }

Johnny is a bad boy, so he commands you to do this for him!

 

 

Input

Input contains two lines.

First line contains two integer n ( 1 <= n <= 20 ), k ( 1<=  k <=10⁹)

Second line contains n integer a₁ ~ a_n ( 1 <= a_i <= 10⁷ )

 

Output

Output only contains one integer that is sum of available ways to pick numbers, which summation is equal to k.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"Death is like the wind, always by my side.", said by a famous streamer, Mr. Yasuoo.

Mr. Yasuoo is known for his skill "Slides up".

---

When Mr. Yasuoo slides across a string S, he will be asked t questions.

In each question, he should respond the number of occurrences of substring s, given a interval of [ l, r ].

Specifically, if the string S is "hasahasasaki" and the substring s is "sa", Mr. Yasuoo should answer 2 given the interval of [3, 9].

Since the interval [3~9]  indicates "sahasas",  the number of occurrences of substring "sa" is then 2.

Note that the index of string starts from 1 and contains only 'a' ~ 'z'.

Help Mr. Yasuoo to answer these questions before he starts feeding, ASAP!

⠄⠄⠄⠄⠄⠄⠄
 ⠄⠄⠄⠄⠄⠄⠄⠈⠉⠁⠈⠉⠉⠙⠿⣿⣿⣿⣿⣿
 ⠄⠄⠄⠄⠄⠄⠄⠄⣀⣀⣀⠄⠄⠄⠄⠄⠹⣿⣿⣿
 ⠄⠄⠄⠄⠄⢐⣲⣿⣿⣯⠭⠉⠙⠲⣄⡀⠄⠈⢿⣿
 ⠐⠄⠄⠰⠒⠚⢩⣉⠼⡟⠙⠛⠿⡟⣤⡳⡀⠄⠄⢻
 ⠄⠄⢀⣀⣀⣢⣶⣿⣦⣭⣤⣭⣵⣶⣿⣿⣏⠄⠄⣿
 ⠄⣼⣿⣿⣿⡉⣿⣀⣽⣸⣿⣿⣿⣿⣿⣿⣿⡆⣀⣿
 ⢠⣿⣿⣿⠿⠟⠛⠻⢿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣼
 ⠄⣿⣿⣿⡆⠄⠄⠄⠄⠳⡈⣿⣿⣿⣿⣿⣿⣿⣿⣿
 ⠄⢹⣿⣿⡇⠄⠄⠄⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
 ⠄⠄⢿⣿⣷⣨⣽⣭⢁⣡⣿⣿⠟⣩⣿⣿⣿⠿⠿⠟
 ⠄⠄⠈⡍⠻⣿⣿⣿⣿⠟⠋⢁⣼⠿⠋⠉⠄⠄⠄⠄
 ⠄⠄⠄⠈⠴⢬⣙⣛⡥⠴⠂⠄⠄⠄⠄⠄⠄⠄⠄⠄...
(the photo of the famous streamer)

Input

Input should contain multiple lines.

First line indicates the string S ( 1<= length of S <= 10³ )

Second line gives the substring s ( 1<= length of s <= 10³ )

the string contains only lower case a~z.

Third line contains one integer t ( 1<= t <= 2*10⁶ )

each of the following t lines gives two integer [l , r], where ( 1<= l <= r <= length of S)

Output

For each question, you are asked to print the the number of occurrences of substring s.

Your program should present a single '\n' at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss