Cho bàn bi băng có kích cỡ ~N * M~ đơn vị, ta quy ước các hàng được đánh số từ trái sang phải, các cột được đánh số từ trên xuống dưới. Ô ~(x, y)~ là giao của hàng ~x~ và cột ~y~.

Có ~Q~ truy vấn, mỗi truy vấn có dạng ~(x,y,\alpha,k)~, tức là giả sử bạn đặt bi cái ở ô ~(x, y)~, căn một góc ~\alpha~ và bắn bi với một lực sao cho bi cái sẽ di chuyển đúng ~\sqrt2 \times k~ đơn vị. Hỏi bi cái sẽ đập băng bao nhiêu lần (nếu ta giả sử rằng không có lực ma sát giữa mặt bàn và bi cái và bi cái sẽ lập tức dừng lại sau khi đi đúng ~k~ đơn vị). Nếu bi cái chạm vào góc và bật lại, ta coi như bi cái chỉ đập băng ~1~ lần.

Bởi vì đề ban đầu quá dễ, nên ~\alpha~ sẽ được giới hạn bởi các góc chéo (góc ~45^{\circ}, 135^{\circ}, 225^{\circ}, 315^{\circ}~).

Các góc ở đây được hiểu theo nghĩa là góc lượng giác. Bạn có thể xem kỹ hơn về bảng giá trị góc lượng giác trong hình dưới đây.

Input

• Dòng đầu tiên nhập hai số ~N~, ~M~ ~(3 \leq N, M \leq 10^9)~ là số hàng và số cột của bàn bi.
• Dòng thứ hai nhập vào một số ~Q~ ~(1 \leq Q \leq 10^5)~ là số truy vấn.
• ~Q~ dòng sau, mỗi dòng nhập vào bốn số ~x, y, \alpha, k~ ~(1 \leq x \leq N, 1 \leq y \leq M, \alpha \in \left \{ 45, 135, 225, 315 \right \}, 1 \leq k \leq 10^{18})~ lần lượt là vị trí xuất phát, góc bắn và quãng đường mà bi cái sẽ di chuyển.

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ thể hiện cho truy vấn thứ ~i~.

Sample Input

3 4
2
2 2 315 4
2 3 315 4

Sample Output

3
2

Scoring