Các dấu ngoặc xuất hiện rất nhiều trong các biểu thức toán học để thể hiện thứ tự tính toán. Giờ đây ta bỏ hết các hạng tử toán tử đi, chỉ giữ lại các dấu ngoặc, biểu thức mà ta thu được gọi là một dãy ngoặc đúng. Cụ thể hơn:

• Xâu rỗng là biểu thức ngoặc đúng

• Nếu ~A~ là biểu thức ngoặc đúng thì (~A~), [~A~], {~A~}, <~A~> cũng là dãy ngoặc đúng

• Nếu ~A~ và ~B~ là biểu các thức ngoặc đúng thì ~AB~ cũng là biểu thức ngoặc đúng

Cho một xâu ~S~ là một biểu thức ngoặc (có thể không đúng).

Yêu cầu: Hãy đếm số xâu con liên tiếp của ~S~ là dãy ngoặc đúng.

Input

Vào từ file văn bản tbrackets.inp:

• Một xâu ~S~ (~|S| \le 10^5~)

Output

Đưa ra file văn bản tbrackets.out:

• Một số nguyên duy nhất là kết quả bài toán.

Scoring

Sample Input 1

()()()

Sample Output 1

6

Sample Input 2

[]{()}

Sample Output 2

4

Cho số nguyên dương ~n~ và dãy số nguyên không âm ~a_1,a_2,...,a_n~. Ta định nghĩa khoảng cách giữa hai số ~x~ và ~y~ là số lần ít nhất phải thực hiện các thao tác sau để biến ~x~ thành ~y~:

• Chọn một lũy thừa của ~2~, kí hiệu là ~2^z~.

• Thực hiện phép gán ~x = x~ ~\oplus~ ~2^z~

Trong đó ~\oplus~ là phép toán ~XOR~ được cho bởi bảng giới đây:

Việc thực hiện phép ~XOR~ trên hai số nguyên là thực hiện phép ~XOR~ trên từng bit trong biểu diễn nhị phân của hai số.

Yêu cầu: Với mỗi số ~a_1,a_2,...,a_n~; hãy tìm một số khác trong dãy có khoảng cách tới số đó là bé nhất.

Input

Vào từ file văn bản mind.inp:

• Dòng đầu tiên chứa số nguyên dương ~n~ (~2\le n \le 5 \times 10^5~) là số phần tử của dãy.

• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1,a_2,...,a_n~ (~a_i \le 5 \times 10^5~) mô tả dãy được cho.

Output

Đưa ra file văn bản mind.out:

• ~n~ số nguyên, mỗi số nguyên là khoảng cách gần nhất ứng với một phần tử trong phương án tối ưu tìm được.

Scoring

Sample Input 1

6
1 2 4 3 8 15

Sample Output 1

1 1 2 1 2 2

Thị trấn nọ có ~n~ hộ dân đang sinh sống, hộ dân thứ ~i~ sống ở vị trí (~x_i, y_i~) trên hệ trục tọa độ ~Oxy~. Chính phủ, đứng đầu là thủ tướng Trần, muốn xây dựng một con đường cao tốc với kinh phí đầu tư cực kì cao, là cơ sở để phát triển kinh tế đất nước.

Do thị trấn nằm trên đường cao tốc, tất cả hộ dân sẽ phải di dời đến khu vực khác. Tuy nhiên, ngài Trần sẽ chỉ cho dỡ bỏ ~n-1~ ngôi nhà và giữ lại ngôi nhà cách xa cao tốc nhất nhằm giữ lại di tích cuối cùng của một thị trấn có lịch sử lâu đời.

Chính phủ đã đề xuất ~q~ phương án, phương án thứ ~j~ là xây dựng cao tốc được biểu diễn bởi đồ thị hàm số ~y = a_jx + b_j~.

Yêu cầu: Với mỗi phương án, hãy giúp thủ tướng Trần tìm hộ dân cách xa cao tốc nhất nếu đó là phương án được chọn để xây dựng.

Input

Dữ liệu vào từ file văn bản highway.inp

• Dòng đầu nhập vào hai số ~n, q~ (~1 \le n, q \le 10^5~) lần lượt là số hộ dân đang sinh sống trong thị trấn và số phương án đề xuất.

• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x_i~ và ~y_i~ (~-10^9 \le x_i, y_i \le 10^9~) thể hiện tọa độ của hộ dân thứ ~i~.

• ~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~a_j~ và ~b_j~ (~-10^9 \le a_j, b_j \le 10^9~) là đường cao tốc được biểu diễn bởi đồ thị hàm số ~y = a_jx + b_j~.

Output

Kết quả in ra file văn bản highway.out

• In ra ~q~ dòng, dòng thứ ~i~ chứa một số nguyên là chỉ số của hộ dân xa nhất đối với phương án xây dựng cao tốc thứ ~i~. Nếu tồn tại nhiều đáp án, hãy in ra đáp án bất kỳ.

Scoring

Sample Input 1

4 3
1 5
-2 4
1 1
0 5
3 2
-1 1
5 -3

Sample Output 1

2
1
2