Farmer John ma na swojej farmie wiele jabłoni. Każde drzewo owocowe posiada kolisty obszar, który zapewnia cień podczas upalnego lata. Farmer John tworzy zagrodę dla swoich krów i rozważa kilka lokalizacji. Dla każdego ogrodzonego obszaru chce wiedzieć, jaki procent tego terenu jest zacieniony.

Każdy proponowany ogrodzony obszar ma kształt prostokąta o bokach równoległych do osi układu współrzędnych, określonego przez jego lewy dolny róg oraz szerokość i wysokość. Oblicz procent zacienionego obszaru dla każdego z proponowanych prostokątów.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $n$ ($1 \le n \le 3\,000$) oraz $q$ ($1 \le q \le 3\,000$), gdzie $n$ to liczba jabłoni w sadzie Farmera Johna, a $q$ to liczba prostokątnych ogrodzonych obszarów, które chce przetestować.

Każda z kolejnych $n$ linii zawiera trzy liczby całkowite $x, y$ ($-10^6 \le x, y \le 10^6$) oraz $r$ ($1 \le r \le 10^6$). Każda linia opisuje kolisty zacieniony obszar drzewa, gdzie $(x, y)$ to jego środek, a $r$ to promień. Zauważ, że drzewa mogą mieć bardzo powykręcane pnie, więc możliwe jest, że dwa zacienione obszary mają ten sam środek lub są nawet identyczne.

Każda z kolejnych $q$ linii zawiera cztery liczby całkowite $x, y$ ($-10^6 \le x, y \le 10^6$), $w$ oraz $h$ ($1 \le w, h \le 10^6$). Każda linia opisuje prostokątny obszar, który Farmer John chce przetestować. Prostokąt ma przekątną od $(x, y)$ do $(x + w, y + h)$.

Wyjście

Wypisz $q$ linii, z których każda zawiera pojedynczą liczbę rzeczywistą, będącą procentem zacienienia danego prostokąta, w skali od 0 do 100. Wypisz wartości procentowe dla prostokątów w kolejności ich występowania na wejściu. Każda wartość powinna mieścić się w granicach błędu względnego lub bezwzględnego $10^{-5}$ względem odpowiedzi sędziego.

Przykład

Wejście 1

2 2
0 0 3
2 1 4
0 0 3 3
-3 -3 6 6

Wyjście 1

100.000000000
89.536784729

Wejście 2

4 3
-1 -1 3
1 -1 3
-1 1 3
1 1 3
-4 -4 8 8
-1 -4 2 8
-3 -1 12 3

Wyjście 2

87.222142378
98.586991373
57.862330458