Алыс бір өлкеде қамал бар. Егер бағыттарды Декарттық координаталар жүйесі арқылы сипаттасақ, қамалдың аумағын центрі координаталар басында орналасқан радиусы $R$ дөңгелек ретінде қарастыруға болады. Қамал аумағының шекарасы биік қабырғалармен қоршалған, сондықтан қамалдың ішінен сыртын көру мүмкін емес.

Қамалдың ішінде бірнеше ғимарат бар. Ыңғайлы болу үшін ғимараттардың шекаралары қабырғалары координата осьтеріне параллель болатын, өзара қиылысуы мүмкін $n$ тіктөртбұрышпен беріледі. Қамал ішіндегі нүкте тіктөртбұрыштардың кез келген біреуінің қатаң ішінде жатса, ол бөгелген деп есептеледі (тіктөртбұрыштардың шекарасындағы нүктелер ішінде жатыр деп есептелмейді).

Кішкентай S — осы қамалдың күзетшісі. Ол қамал ішіндегі бөгелмеген бір $(x, y)$ нүктесінде тұр. Кішкентай S қамал ішіндегі басқа бір $(x', y')$ нүктесін тек $(x, y) - (x', y')$ кесіндісіндегі әрбір нүкте (екі шеткі нүктені қоса алғанда) бөгелмеген болған жағдайда ғана күзете алады. Тапсырма — Кішкентай S күзете алатын нүктелер жиынының ауданын, яғни Кішкентай S бақылай алатын қамал жерінің ауданын есептеу.

Кіріс деректер

Бұл есеп бірнеше тест жиынынан тұрады. Кіріс деректердің бірінші жолында тест жиындарының санын білдіретін бүтін сан $T$ ($1 \le T \le 10^5$) берілген.

Әрбір тест жиыны үшін:

• Бірінші жолда қамалдың радиусы мен тіктөртбұрыштар санын білдіретін екі бүтін сан $R, n$ ($0 < R \le 10^6, 0 \le n \le 10^5$) берілген.
• Келесі $n$ жолдың әрқайсысында тіктөртбұрышты сипаттайтын төрт бүтін сан $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$) берілген, мұндағы $(x_1, y_1)$ — сол жақ төменгі бұрыштың координаталары, ал $(x_2, y_2)$ — оң жақ жоғарғы бұрыштың координаталары. Барлық тіктөртбұрыштар қамал аумағының қатаң ішінде орналасқанына және аумақ шекарасына тимейтініне кепілдік беріледі.
• Соңғы жолда Кішкентай S-тің координаталарын білдіретін екі бүтін сан $x, y$ ($|x|, |y| \le 10^6, x^2 + y^2 < R^2$) берілген. $(x, y)$ нүктесі бөгелмегеніне кепілдік беріледі.

Барлық тест жиындары бойынша $n$ сандарының қосындысы $10^5$-тен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиыны үшін бір жолда Кішкентай S қамал ішінде күзете алатын нүктелер жиынының ауданын білдіретін нақты санды шығарыңыз.

Егер стандартты жауаппен салыстырғандағы салыстырмалы немесе абсолютті қателік $10^{-6}$-нен кіші болса, жауап дұрыс деп есептеледі. Басқаша айтқанда, егер сіздің шығысыңыз $a$, ал стандартты жауап $b$ болса, сіздің жауабыңыз тек $\frac{|a-b|}{\max(1,b)} \le 10^{-6}$ болғанда ғана дұрыс деп саналады.

Мысал

Кіріс деректер

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

Шығыс деректер

5.598332050807308
513.142778328943998

Ескертпе

Бірінші тест жиыны үшін сәйкес сурет төмендегідей:

Екінші тест жиыны үшін сәйкес сурет төмендегідей: