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