Cho một đa giác ~n~ điểm và không tự cắt chính nó. Đa giác có thể không lồi và có thể chứa góc ~180~ độ.

Cho ~m~ đường thẳng. Với mỗi đường thẳng, hãy tìm độ dài của phần chung giữa đường thẳng đó và đa giác đã cho.

Input

Dòng đầu tiên chứa các số nguyên ~n~ và ~m~ ~(3 \le n \le 1000; 1 \le m \le 100)~.

~n~ dòng tiếp theo, mỗi dòng ghi toạ độ các điểm của đa giác (theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ). Các điểm phân biệt với nhau.

~m~ dòng tiếp theo, mỗi dòng gồm toạ độ hai điểm phân biệt trên đường thẳng, mô tả đường thẳng đó.

Mọi toạ độ trong input đều là số thực với tối đa ~2~ chữ số ở phần thập phân. Ngoài ra, các toạ độ này có giá trị tuyệt đối không quá ~10^5~.

Output

In ra ~m~ dòng, dòng thứ ~i~ chứa độ dài của phần chung giữa đường thẳng thứ ~i~ và đa giác. Đáp án sẽ được tính là đúng nếu sai số không vượt quá ~10^{-6}~.

Sample Input

4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1

Sample Output

1.41421356237309514547
1.00000000000000000000
0.00000000000000000000