Као награду за изузетан успех на првом кругу квалификација, Алекса је добио на поклон парче кекса у облику правоугаоника димензија \(W \times H\), и поставио га је у раван тако да му се темена налазе на координатама \((0, 0), (W, 0), (W, H)\) и \((0, H)\). Његов архинепријатељ Павле се намерачио на ово парче кекса и планира да га поједе. Павлетова вилица се може описати кругом полупречника \(R\). Током \(i\)-тог минута деси се један од следећа два догађаја:

• \(1\) \(x_i\) \(y_i\): Павле позиционира своју вилицу тако да се центар круга налази у тачки са координатама \((x_i, y_i)\), затим гризе кекс односно уклања сав садржај кекса који се налази у његовој вилици,

• \(2\) \(x_i\): Алекса узима лењир, поставља га тако да буде паралелан са \(y\)-осом, тако да пролази кроз тачку \((x_i, 0)\) и мери дужину тренутно преосталог парчета кекса које се преклапа са ивицом лењира.

Да ли можете да предвидите које резултате мерења ће Алекса добити?

Опис улаза

У првој линији стандардног улаза налазе се четири природна броја, одвојена размаком: \(W, H, R, Q\). У наредних \(Q\) линија, налазе се два или три броја: \(1, x_i, y_i\) или \(2, x_i\), одвојена размаком, који описују \(i\)-ти догађај.

Опис излаза

За сваки догађај типа \(2\) исписати један реалан број - резултат одговарајућег мерења. Уколико је тачно решење тог мерења \(b\), а ваш програм исписује број \(a\), ваш излаз ће се сматрати тачним уколико важи \(\frac{|a-b|}{\max(1,b)} \leq 10^{-6}\).

Пример 1

Улаз

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

Излаз

2.000000000000
2.000
1.267949192431
1

Објашњење примера

Пре него што је Павле одгризао парче кекса, на било којој \(x\)-координати била би измерена вредност \(H = 2\). Након што је одгризао парче кекса, на координати \(x = 0\) је дужина \(2\), на \(x = 1\) је \(3 - \sqrt{3} \approx 1.268\) а на \(x = 2\) је \(1\) (видети слику).

Ограничења

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

Тест примери су подељени у 5 дисјунктних група:

• У тест примерима вредним 10 поена: \(R = 1\).
• У тест примерима вредним 10 поена: \(R = 2\).
• У тест примерима вредним 10 поена: \(Q \times W \leq 10^6\).
• У тест примерима вредним 20 поена: Сваки догађај типа \(2\) се јавља након свих догађаја типа \(1\).
• У тест примерима вредним 50 поена: Без додатних ограничења.

Напомена

Да бисте избегли проблеме са прецизношћу, користите типове double или long double у језику C++, и исписујте решење на бар \(9\) децимала.