Король Полігонії Тріанг IV помішаний на реформах. Щоб увійти у світову історію, він вирішив провести територіальну реформу у своії країні. Крїана Полігонія має форму простого многокутника, тобто її границя не має самоперетинів та самодотикань. У Полігонії велику роль відіграють внутрішні діагоналі — відрізки, які з'єднують вершини державного кордону і які повністю проходять по території країни, не дотикаючись границь. При цьому форма Полігонії така, що ніякі дві внутрішні діагоналі не лежать на одній прямій.
Замість традиційного поділу держави на адміністративні одиниці король Тріанг IV вирішив розділити свою країну на адміністративні трикутники внутрішніми діагоналями. Для скорочення адміністративного апарату король звелів підготувати такий план поділу країни, у якому кількість адміністративних трикутників буде мінімальною.
Потрібно написати програму, яка виконує поділ Полігонії внутрішніми діагоналями на мінімально можливе число адміністративних трикутників.
У першому рядку вхідного файлу записано число N (3 ≤ N ≤ 20) — кількість вершин многокутника, який утворює границю Полігонії. У наступних N рядках знаходяться по 2 цілих числа, які за абсолютною величиною не перевищують 10000 — координати вершин у порядку обходу многокутника проти годинникової стрілки. Гарантується, що ніякі три послідовні вершини многокутника не лежать на одній прямій, і він не має самоперетинів та самодотикань. Також гарантується, що ніякі дві діагоналі, що містяться всередині многокутника, не лежать на одній прямій.
У перший рядок вихідного файлу виведіть найменшу кількість адміністративних трикутників, на які можна розбити Полігонію.
У другому рядку виведіть кількість різних внутрішніх діагоналей K, при допомозі яких можна здійснити дане разбиття.
У кожен з наступнх K рядків виведіть 4 цілих числа — координати початку та кінця відповідної діагоналі розбиття, яке повністю лежить всередині многокутника і не проходить по його границі.
Якщо шуканих разбиттів декілька, виведіть довільне з них.