Khảo cổ khu Hoàng Thành

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 tọa độ Đề 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ị.

Dữ liệu vào

• 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ố nguyên $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)$ và điểm $(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 khu Hoàng Thành.

Dữ liệu ra

In ra $m$ dòng, dòng thứ $j$ là số bức tường ít nhất cần vượt qua ở giả định thứ $j$.

Ràng buộc

• $1\le n,m\le {10}^6$.
• $-{10}^9<x_i<u_i<{10}^9$; $-{10}^9<y_i<v_i<{10}^9$.
• $-{10}^9<x_s,y_s,x_f,y_f<{10}^9$.
• Hai bức tường của hai phòng khác nhau không có điểm chung; hai điểm của mỗi giả định không nằm trên bức tường nào.

Subtasks

Điểm được tính theo từng test.

• Có $30\%$ số test ứng với $30\%$ số điểm của bài thỏa mãn: $n,m\le {10}^2$.
• $40\%$ số test khác ứng với $40\%$ số điểm của bài thỏa mãn: $n,m\le {10}^4$.
• $30\%$ số test còn lại ứng với $30\%$ số điểm của bài thỏa mãn: $n,m\le {10}^6$.

Ví dụ