Az első kvalifikációs versenyen elért kiváló eredményéért ajándékul Aleksa \(W \times H\) méretű, téglalap alakú kekszet kapott, amelyet úgy helyezett el a síkban, hogy csúcsainak koordinátái \((0, 0), (W, 0), (W, H)\) és \((0, H)\) legyenek. Örökös vetélytársa Pavle szemet vetett erre a kekszre, és elhatározta, hogy megeszi azt. Pavle állkapcsát \(R\) sugarú körnek tekinthetjük. Az \(i\)-edik percben a következő két esemény egyike következik be:

• \(1\) \(x_i\) \(y_i\): Pavle úgy helyezi el állkapcsát, hogy a kör középpontja az \((x_i, y_i)\) koordinátában legyen, ezután leharapja, illetve eltünteti a keksznek azt a részét, amely állkapcsán belül helyezkedik el.
• \(2\) \(x_i\): Aleksa felvesz egy vonalzót, és úgy helyezi el, hogy az párhuzamos legyen az \(y\) tengellyel úgy, hogy áthaladjon az \((x_i, 0)\) ponton, majd leméri a pillanatnyilag megmaradt kekszdarab hosszát, ahol éppen átfedi a vonalzó élét.

Előreláthatjátok-e Aleksa által mért eredményeket?

Bemenet

A szabványos bemenet első sorában négy természetes szám \(W, H, R, Q\) található, szóközökkel elválasztva. A következő \(Q\) sorban két vagy három szám található: \(1, x_i, y_i\) vagy \(2, x_i\), szóközzel elválasztva, amelyek az \(i\)-edik eseményt írják le.

Kimenet

Minden \(2\) típusú eseményre kiíratni egy valós számot, a megfelelő mérés eredményét. Amennyiben az adott mérés pontos eredménye \(b\), a program pedig \(a\) értéket ír ki, a kimenetet pontosnak tekintjük, ha érvényes, hogy \(\frac{|a-b|}{\max(1,b)} \leq 10^{-6}\).

1. példa

Bemenet

3 2 2 5
2 1
1 2 3
2 0
2 1
2 2

Kimenet

2.000000000000
2.000
1.267949192431
1

A példa magyarázata

Mielőtt Pavle leharapta volna a keksz egy darabját, bármely x koordinátán a mért érték \(H = 2\). Miután leharapta a keksz egy részét az \(x = 0\) koordinátán a hossz \(2\), \(x = 1\) értékre \(3 - \sqrt{3} \approx 1.268\) és \(x = 2\) értékre \(1\) (lásd az ábrán).

Korlátozások

• \(1 \leq W, H, R, Q \leq 10^5\)
• \(0 \leq x_i \leq W\)
• \(H \leq y_i \leq H+R\)

A tesztpéldák 5 független csoportba oszthatók:

• Tesztpéldák, melyek \(10\) pontot érnek: \(R = 1\).
• Tesztpéldák, melyek \(10\) pontot érnek: \(R = 2\).
• Tesztpéldák, melyek \(10\) pontot érnek: \(Q \times W \leq 10^6\).
• Tesztpéldák, melyek \(20\) pontot érnek: minden 1 és 2 típusú eseményre érvényes, hogy 2 típusú eseményt 1 típusú esemény előz meg.
• Tesztpéldák, melyek \(50\) pontot érnek: nincs külön korlátozás.

Megjegyzés

Hogy kiküszöböljétek a precizitási problémákat, a C++ nyelvben használjatok double vagy long double értéktípusokat, és az eredményeket pedig legalább \(9\) tizedes pontossággal írassátok ki.