8707번 - Dolary i Euro 다국어

문제

Wallace jest znanym gangsterem - prawdziwym G. Jak każdy gangster ma dużo brudnego szmalu, który lubi wydawać na klejnoty. Dla bezpieczeństwa nie trzyma jednak pieniędzy w jednym portfelu lecz w wielu. Wallace ma zamiar wybrać się z ziomalami na miasto.

Chce zabrać około połowy swoich portfeli, ale z drugiej strony chce mieć wystarczająco dużo pieniędzy. Dokładniej Wallace ma 2n - 1 portfeli, a w każdym ma pewną ilość dolarów i pewną ilość euro. Na przejażdżkę chce zabrać dokładnie n portfeli, tak aby suma dolarów w tych n portfelach była większa bądź równa połowie sumy dolarów we wszystkich 2n - 1 portfelach oraz aby suma euro w wybranych n portfelach była większa bądź równa połowie sumy euro we wszystkich portfelach.

Wallace zna się na robieniu szmalu, Ty znasz się na programowaniu. Wiesz, co masz robić.

입력

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita t oznaczająca liczbę zestawów danych. Następnie występuje opis każdego zestawu danych.

W pierwszej linii zestawu danych znajduje się jedna liczba całkowita n (1 ≤ n ≤ 500 000) oznaczająca, że Wallace ma 2n - 1 portfeli. W kolejnych 2n - 1 wierszach znajdują się opisy kolejnych portfeli. Każdy wiersz zawiera dwie liczby całkowite d_i, e_i (0 ≤ d_i, e_i ≤ 10⁹) oznaczających, że portfel i-ty zawiera d_i dolarów oraz e_i euro.

Możesz założyć, że suma n we wszystkich zestawach danych nie przekroczy 2 500 000.

출력

Wyjście powinno zawierać odpowiedzi dla kolejnych zestawów danych.

W pierwszym wierszu odpowiedzi dla zestawu powinno znaleźć się jedno słowo 'Yo', jeżeli można wybrać n portfeli zgodnie z oczekiwaniami Wallaca, albo 'Nah', jeżeli nie jest to możliwe. Jeżeli wynik istnieje, to w drugiej linii powinno znaleźć się n liczb całkowitych oznaczających numery portfeli, które należy wybrać. Portfele są numerowane kolejnymi numerami całkowitymi: 1, 2, ..., 2n - 1 zgodnie z kolejnością na wejściu.

제한

힌트