Di sebuah negeri yang jauh, terdapat sebuah benteng. Jika kita menyatakan orientasinya menggunakan sistem koordinat Kartesius, wilayah benteng dapat dipandang sebagai lingkaran yang berpusat di titik asal dengan jari-jari $R$. Batas wilayah benteng dikelilingi oleh tembok tinggi, dan mustahil untuk melihat ke luar dari dalam benteng.

Di dalam benteng, terdapat beberapa bangunan. Untuk memudahkan, batas-batas bangunan direpresentasikan oleh $n$ persegi panjang yang mungkin saling tumpang tindih dan sisi-sisinya sejajar dengan sumbu koordinat. Sebuah titik di dalam benteng dianggap terhalang jika titik tersebut berada строго (secara ketat) di dalam salah satu persegi panjang (titik pada batas persegi panjang tidak dianggap berada di dalam).

Little S adalah penjaga benteng ini. Ia berdiri di suatu titik $(x, y)$ yang tidak terhalang di dalam benteng. Little S dapat menjaga titik lain $(x', y')$ di dalam benteng jika dan hanya jika setiap titik pada ruas garis $(x, y) - (x', y')$ (termasuk kedua titik ujungnya) tidak terhalang. Tugasnya adalah menghitung luas himpunan titik yang dapat dijaga oleh Little S, yang menyatakan luas tanah benteng yang dapat diawasi oleh Little S.

Masukan

Soal ini berisi beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^5$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji:

• Baris pertama berisi dua bilangan bulat $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$), yang masing-masing menyatakan jari-jari benteng dan banyaknya persegi panjang.
• $n$ baris berikutnya masing-masing berisi empat bilangan bulat $x_1, y_1, x_2, y_2$ ($|x_1|, |x_2|, |y_1|, |y_2| \le 10^6, x_1 < x_2, y_1 < y_2$), yang mendeskripsikan sebuah persegi panjang, dengan $(x_1, y_1)$ menyatakan koordinat pojok kiri bawah dan $(x_2, y_2)$ menyatakan koordinat pojok kanan atas. Dijamin bahwa semua persegi panjang berada secara ketat di dalam wilayah benteng dan tidak menyentuh batas wilayah.
• Baris terakhir berisi dua bilangan bulat $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$), yang menyatakan koordinat Little S. Dijamin bahwa titik $(x, y)$ tidak terhalang.

Dijamin bahwa jumlah total $n$ di seluruh kasus uji tidak melebihi $10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan riil yang menyatakan luas himpunan titik yang dapat dijaga oleh Little S di dalam benteng.

Jawaban akan dianggap benar jika galat relatif atau absolut dibandingkan dengan jawaban standar kurang dari $10^{-6}$. Dengan kata lain, jika keluaran Anda adalah $a$ dan jawaban standar adalah $b$, keluaran Anda dianggap benar jika dan hanya jika $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$.

Contoh

Masukan

2
2 3
-1 -1 0 0
-1 -1 0 1
0 -1 1 0
1 1
26 5
-3 -23 10 21
-15 3 -5 14
-12 -18 -10 -15
-5 -6 -2 8
7 -23 10 -19
-10 0

Keluaran

5.598332050807308
513.142778328943998

Catatan

Untuk kasus uji pertama, gambar yang sesuai adalah sebagai berikut:

Untuk kasus uji kedua, gambar yang sesuai adalah sebagai berikut: