Керування камерою
"ACM48" — один із найпопулярніших танцювально-вокальних колективів у Японії. Цієї зими ACM48 планує світове турне з концертами. Ви приєдналися до туру як інженер з камер.
Ваша роль полягає в розробці програмного забезпечення для управління камерою на сцені. Для простоти вважатимемо, що сцена є 2-вимірним простором. Ви можете обертати камеру в будь-якому напрямку за допомогою програмного забезпечення, але не можете змінювати її координати.
Під час сценічного виступу кожна учасниця ACM48 рухається за своїм маршрутом і виконує призначені їй вокальні партії. Маршрут заданий як ламана лінія.
Ви повинні постійно фокусувати камеру на учасниці під час виступу. Ви можете змінити учасницю, на якій фокусується камера, лише якщо поточна та наступна учасниці знаходяться в одному напрямку від камери.
Ваше завдання — написати програму, яка зчитує план сценічного виступу і обчислює максимальний час, протягом якого ви можете фокусувати камеру на учасницях, які співають.
Ви можете припустити, що виконуються наступні умови:
Ви можете фокусувати камеру на будь-якій учасниці на початку виступу.
Жоден маршрут учасниці не проходить через камеру.
Кожна учасниця залишається на останніх координатах після того, як досягне їх.
Вхідні дані
Вхід містить декілька тестових випадків. Кожен тестовий випадок має наступний формат:
N c_x c_y Інформація про 1-шу учасницю ... Інформація про N-ту учасницю
N (1 ≤ N ≤ 50) — кількість учасниць. (c_x, c_y) — координати камери. Далі йде інформація про N учасниць.
Інформація про i-ту учасницю має наступний формат:
M_i x_{i,1} y_{i,1} t_{i,1} ... x_{i,Mi} y_{i,Mi} t_{i,Mi} L_i b_{i,1} e_{i,1} ... b_{i,Li} e_{i,Li}
M_i (1 ≤ M_i ≤ 100) — кількість точок у маршруті. (x_{i,j}, y_{i,j}) — координати j-тої точки у маршруті. t_{i,j} (0 = t_{i,0} < t_{i,j} < t_{i,j+1} ≤ 10^3 для 0 < j) — час, коли i-та учасниця досягає j-тих координат. L_i (0 ≤ L_i ≤ 100) — кількість вокальних частин. b_{i,k} та e_{i,k} (0 ≤ b_{i,k} < e_{i,k} < b_{i,k+1} < e_{i,k+1} ≤ 10^3) — початок і закінчення k-тої вокальної частини відповідно.
Усі вхідні значення є цілими числами. Ви можете припустити, що абсолютне значення всіх координат не перевищує 10^3.
N = 0 позначає кінець введення. Ви не повинні обробляти це як тестовий випадок.
Вихідні дані
Для кожного набору даних виведіть максимальний час, протягом якого ви можете фокусувати камеру на співаючих учасницях з абсолютною похибкою не більше 10^{−6}. Ви можете вивести будь-яку кількість цифр після десяткової точки.