Các nhà khảo cổ mới phát hiện ra một khu Hoàng Thành được xây dựng từ nhiều thế kỷ trước. Theo nhận định ban đầu, Hoàng Thành gồm nhiều căn phòng khép kín bởi bốn bức tường song song hoặc vuông góc với nhau. Để tiến hành nghiên cứu, các nhà khảo cổ đã xây dựng bản đồ các bức tường của khu Hoàng Thành. Cụ thể, bản đồ được mô tả trên mặt phẳng toạ độ Đề các vuông góc \(Oxy\), trong đó các bức tường là các đoạn thẳng song song với một trong hai trục tọa độ. Theo các dữ liệu thu thập được, có \(n\) căn phòng được đánh số từ \(1\) đến \(n\), căn phòng thứ \(i (1\le i\le n)\) là một hình chữ nhật có tọa độ trái dưới là \((x_{i},y_{i})\) và tọa độ phải trên là \((u_{i},v_{i})\). Bốn bức tường tương ứng là các đoạn thẳng nối tọa độ \((x_{i},y_{i})\) với \((x_{i},v_{i}), (x_{i},v_{i})\) với \((u_{i},v_{i}), (u_{i},v_{i})\) với \((u_{i},y_{i})\) và \((u_{i},y_{i})\) với \((x_{i},y_{i})\). Hai đoạn thẳng mô tả hai bức tường của hai phòng khác nhau không có điểm chung. Một thiết bị đặc biệt được các nhà khảo cổ sử dụng để khảo sát khu Hoàng Thành. Thiết bị nhỏ gọn nhưng mỗi khi cần điều khiển thiết bị để vượt qua một bức tường là rất khó khăn. Với một giả định, ban đầu thiết bị được đặt tại tọa độ \((x_{s},y_{s})\) và cần di chuyển tới tọa độ \((x_{f},y_{f})\), các nhà khảo cổ muốn tính toán số bức tường ít nhất cần vượt qua khi điều khiển thiết bị.

Yêu cầu: Cho các thông tin về khu Hoàng Thành và \(m\) giả đỉnh, với mỗi giả định hãy giúp các nhà khảo cổ tính toán số bức tường ít nhất cần vượt qua khi điều khiển thiết bị.

Input

• Dòng đầu gồm hai số nguyên dương \(n,m\);
• Dòng thứ \(i (1\le i\le n)\) trong \(n\) dòng tiếp theo gồm bốn số \(x_{i},y_{i},u_{i},v_{i}\) mô tả căn phòng thứ \(i (-10^{9}<x_{i}<u_{i}<10^{9};-10^{9}<y_{i}<v_{i}<10^{9})\);
• Dòng thứ \(j (1\le j\le m)\) trong \(m\) dòng tiếp theo, mỗi dòng mô tả một giả định gồm bốn số nguyên \(x_{s},y_{s},x_{f},y_{f} (-10^{9}<x_{s},y_{s},x_{f},y_{f}<10^{9})\). Điểm \((x_{s},y_{s} ),(x_{f},y_{f})\) không nằm trên bất kì đoạn thẳng nào mô tả các bức tường của khi Hoàng Thành.

Output

• Ghi ra file thiết bị ra chuẩn gồm m số, mỗi số là đáp án cho truy vấn tương ứng trong dữ liệu vào.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n,m\le 10^{2}\);
• Subtask \(2\) (\(40\%\) số điểm): \(n,m\le 10^{4}\);
• Subtask \(3\) (\(30\%\) số điểm): \(n,m\le 10^{6}\).

Example

3 2
1 0 6 4
2 1 4 3
7 2 9 5
3 2 8 3
8 3 0 0

3
1