Футбол 2
На футбольному полі розміром x × y знаходяться n футболістів. Вони вже дуже втомились і стоять на місці, але чекають, куди впаде м'яч, щоб побігти до нього. Футболіст біжить до мяча у тому випадку, якщо м'яч впав до цього футболіста ближче, ніж до довільного іншого футболіста.
Потрібно визначити для кожного футболіста границі зони, при попаданні у яку він побіжить до м'яча, якщо відомо, що вона являє собою многокутник.
Вхідні дані
У першому рядку вхідного файлу задано три цілих числа x, y та n (2 ≤ x, y ≤ 10^5, 1 ≤ n ≤ 30000). Наступні n рядків містять цілі координати футболістів x_i y_i (0 < x_i < x, 0 < y_i < y). Ніякі два футболіста не стоять в одній точці.
Вихідні дані
У вихідний файл виведіть n рядків. У кожному з рядків перше число - кількість вершин зони k_i, далі k_i чисел - координати вершини x_ij y_ij у порядку обходу проти годинникової стрілки, починаючи з самої нижньої з самих лівих вершин зони. Дійсні числа виводьте з максимальною точністю.