Проходження
Довгий і прямий коридор обладнаний кількома сенсорами. Кожен сенсор має певний радіус дії, в межах якого він може виявляти об'єкти або людей. Якщо частина об'єкта знаходиться в зоні дії сенсора, спрацьовує сигналізація. В іншому випадку нічого не відбувається.
Ітану потрібно пройти через цей коридор, щоб виконати шпигунське завдання на іншому кінці. Питання в тому, чи може він пройти через коридор, не будучи виявленим? Чи може він так легко пройти, що зможе взяти з собою якесь обладнання, або йому доведеться одягнути обтягуючий одяг? Або, можливо, він може відправити робота замість себе?
Ми моделюємо коридор як двовимірний (ігноруючи висоту), обмежений двома прямими лініями. Кожен сенсор розташований всередині коридору або на стіні. Їхні зони дії добре розташовані між двома кінцями коридору. Ми моделюємо людину або робота, що проходить, як коло. Враховуючи планування, який максимальний радіус може мати це коло, щоб можна було пройти через коридор, не будучи виявленим?
Візуальне представлення зразків.
Вхідні дані
На першому рядку одне позитивне число: кількість тестових випадків, не більше 100. Після цього для кожного тестового випадку:
один рядок з одним цілим числом w (1 ≤ w ≤ 100000): ширина коридору. Дві стіни задані лініями x = 0 і x = w.
один рядок з одним цілим числом n (0 ≤ n ≤ 1000): кількість сенсорів у коридорі.
n рядків з трьома цілими числами, розділеними пробілами: x, y і r (0 ≤ x ≤ w, -100000 ≤ y ≤ 100000 і 1 ≤ r ≤ 100000): місце розташування та радіус дії кожного сенсора відповідно.
Два кінці коридору знаходяться на y = -1 і y = +1, або, менш технічно, вони далеко за межами зони дії всіх сенсорів.
Вихідні дані
Для кожного тестового випадку:
один рядок з одним числом з плаваючою комою: радіус найбільшого кругового об'єкта (або людини), який може пройти через коридор, не будучи виявленим, за умови, що об'єкт може (бути) переміщений з абсолютною точністю. Якщо нічого не може пройти, вивід має бути нуль.
Число має бути точним до 10^{-6 } абсолютної точності.