Giới thiệu: Đây là đề thi ICPC

A file name consists of 2 parts: base name and extension name, separated by a dot character. For example, Python source code files have extension name "py", documents have extension name "doc" or "docx". In Windows OS, file names are case insensitive. Please help Salmon: Write a program to input a file name as string and check whether it is considered Python source code file in Windows or not

Input

Only one line contain file name S (1 ≤ |S| ≤ 128). File name will only contain (a->z, A->Z, . and _).

Output

If file is a python file, print "yes", otherwise "no"

Examples

Input

abc.py

Output

yes

Input

abc.bin

Output

no

Giới thiệu: Đây là đề thi ICPC

N + 1 (N is odd number) shoes from (N + 1)/2 pair of shoes the same type with different sizes are lined up in a random order. Aquarius, Taitruong, Loc, David secretly take one of the shoes out and hide it. Salmon need to guess whether the hidden shoe is for left foot or right foot and what is its size. Write a program to solve this game with cheating computer power.

Input

The first line of input contains the one integer N (1 ≤ N ≤ 100000), the number of shoes. The following line contains N integers S1, S2, ..., SN (1 ≤ |Si| ≤ 1000 000 000). Shoe i is for left foot if Si < 0, otherwise it is for right foot. The size of the shoe is |Si|.

Output

Output one integer R where |R| is equal to the hidden shoe is size and it is negative if it is a shoe for left foot, positive otherwise.

Examples

Input

3
1 2 -1

Output

-2

Giới thiệu: Đây là đề thi ICPC

Salmon has a business received a big order for M products, they must deliver as soon as possible but there is nothing left in the warehouse, they have to produce from scratch. They have N workers, worker i produce Ai products every day but take 1 day of leave after every Bi days of work. Calculate what is the earliest day they can finish producing M products to deliver

Input

The first line of input contains 2 integers N and M (1 ≤ N ≤ 100, 1 ≤ M ≤ ~10^{15}~), the number of workers and number of products ordered. The next N lines, each has 2 numbers Ai and Bi (1 ≤ Ai , Bi ≤ ~10^{15}~.

Output

Output one integer, the number of days it take.

Examples

Input

2 30
2 5
1 9

Output

11

Giới thiệu: Đây là đề thi ICPC lậu

H.32 Programming Lab's N pigs, conveniently numbered 1… N, all stand in a line (they seem to do so often so now need very little prompting from SalAqua to line up. them in line). Each pig has a breed ID: 1 for pink, 2 for white and 3 for black. SalAqua would like your help counting the number of pigs of each breed that lie within certain intervals of the ordering.

Input

The first line of input contains N and Q (1≤N≤100,000, 1≤Q≤100,000). The next N lines contain an integer that is either 1, 2, or 3, giving the breed ID of a single pig in the ordering.

The next Q lines describe a query in the form of two integers a,b (a≤b).

Output

For each of the Q queries (a,b), print a line containing three numbers: the number of pigs numbered a…b that are pink (breed 1), white (breed 2), and black (breed 3).

Examples

Input

6 3
2
1
1
3
2
1
1 6
3 3
2 4

Output

3 2 1
1 0 0
2 0 1