Козак Вус нарешті знайшов країну своєї мрії. Вона складається з $n$ міст, між якими не проходить жодна дорога. Звичайно, Вус захотів виправити цю ситуацію, і тому придумав $m$ різних двосторонніх доріг, які можна було би прокласти. За його задумом кожна дорога з'єднує два різні міста. Але виникла проблема: кожне місто $i$ може виділити на побудову доріг $c_i$ копійок, а для кожної дороги $j$ на її побудову пішло б $w_j$ копійок. Тому Козак вирішив, що йому вистачить побудувати декілька доріг так, аби всі міста стали сусідами. Міста називаються сусідами, якщо можливо дорогами країни дістатися з одного міста в інше. При плануванні своїх робіт Козак Вус зрозумів одну річ: коли він будуватиме чергову дорогу, міста будуть об'єднуватися в групи сусідів. Щоб побудувати $j$-ту дорогу, потрібно, щоб міста (або їх сусіди), між якими будується дорога, сумарно мали принаймні $w_j$ копійок (адже спершу потрібно заплатити за дорогу й лише потім будувати). Після побудови дороги бюджети міст об'єднуються, а вартість дороги вираховується з нової спільної казни. Для кожного з $n$ міст ви знаєте число $c_i$ --- кількість копійок, які може витратити місто $i$. Для кожної з $m$ доріг ви знаєте числа $v_i$, $u_i$ та $w_i$, які означають, що дорога $i$ з'єднує міста $v_i$ та $u_i$, а на її побудову потрібно $w_i$ копійок. Скажіть, чи можливо вибрати певну кількість доріг та впорядкувати їх так, щоб усі міста стали сусідами. А якщо це можливо, то знайдіть послідовність доріг, у якій їх потрібно будувати. \Interaction Для того, щоб показати дороги, які потрібно побудувати, використовуйте таку функцію: \begin{verbatim} void add(integer i) \end{verbatim} \begin{itemize} \item Ця функція будує дорогу під номером $i$ ($1\leq i \leq m$). \end{itemize} Вам потрібно реалізувати одну функцію: \begin{verbatim} boolean solve(integer n, integer m, integer g, array of integers c, array of integers v, array of integers u, array of integers w) \end{verbatim} \begin{itemize} \item $n$ --- кількість міст у країні; \item $m$ --- кількість доріг, які можна прокласти; \item $g$ --- номер блока; \item $c_i$ ($|c|=n$) --- початкова кількість копійок у $i$-тому місті; \item $v_i$ та $u_i$ ($|v|=|u|=m$) --- номери вершин, що з'єднує $i$-та дорога; \item $w_i$ ($|w|=m$) "--- кількість копійок, необхідних на побудування $i$-тої дороги; \item ця функція повинна повертати \t{true}, якщо можливо правильно вибрати послідовність доріг, і \t{false}, якщо ні. \end{itemize} Якщо ваша функція повертає \t{true}, то до того, як вона його поверне, вона має зробити виклики функції \t{add} для всіх побудованих доріг у тому порядку, у якому вони побудуються. \InputFile Перший рядок містить три цілі числа $n$, $m$ та $g$ ($1 \leq n \leq 10^6$, $0 \leq m \leq 10^6$, $0 \leq g \leq 7$) --- кількість міст, кількість доріг та номер блока відповідно. Наступний рядок містить $n$ цілих чисел $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^6$) --- початкова кількість копійок в $i$-му місті. Кожний із наступних $m$ рядків містить по три цілі числа $v_i$, $u_i$ та $w_i$ ($1 \leq v_i,u_i \leq n$, $1 \leq w_i \leq 10^6$) --- номер міст, між якими $i$-та дорога, та ціна її побудови відповідно. \OutputFile Якщо функція повертає \t{false}, то в першому рядку буде виведено одне число $-1$. Інакше в першому рядку буде виведено число $q$ --- кількість побудованих доріг. У наступних $q$ рядках буде виведено по одному число $x$ --- номер побудованої дороги. \Note У першому прикладі країна складається з $4$-ох міст, а план Козака Вуса складається з $5$-и доріг. Спочатку будується дорога під номером $4$: міста $2$ та $4$ об'єднаються у групу, а з їхнього загального бюджету сплачується $3$ копійки. На рахунку цієї групи залишається $6$ копійок. Після побудови дороги під номером $2$ бюджет групи буде складати $4$ копійки, адже приєдналося місто $3$ з бюджетом у $2$ копійки, а також витратили $4$ копійки на побудову дороги. Після побудови $3$-ої дороги всі міста стануть сусідами, а їх загального бюджету вистачить, щоб заплатити $5$ копійок за дорогу. У другому прикладі неможливо вибрати дороги та порядок їх побудови так, щоб усі міста стали сусідами й щоб за усі дороги було заплачено. \Scoring \begin{enumerate} \item ($3$ балів) $n \leq 10$; $m = n - 1$; $c_i = 1$; $w_i = 1$; якщо побудувати всі $m$ доріг, усі міста стануть сусідами; \item ($8$ балів) $n,m \leq 10$; \item ($12$ балів) $n,m \leq 10^5$; $c_i = 1$; \item ($14$ балів) $n,m \leq 10^5$; усі $w_i$ однакові; \item ($16$ балів) $n,m \leq 10^3$; \item ($19$ балів) $n,m \leq 10^5$; \item ($12$ балів) $n,m \leq 5 \cdot 10^5$; \item ($16$ балів) без додаткових обмежень. \end{enumerate}