Расскажи историю обо мне и моих друзьях животных.
У Тенцинга есть \(n\) друзей животных. Он пронумеровал их от \(1\) до \(n\).
Однажды Тенцинг захотел поиграть со своими друзьями. Для этого Тенцинг устроит несколько игр.
В рамках одной игры он выберет множество \(S\), которое является подмножеством \(\{1,2,3,...,n\}\) и выберет целое число \(t\). Затем он будет играть в игру с животными из \(S\) в течение \(t\) минут.
Но есть некоторые ограничения:
- Тенцинг очень любит друга \(1\), поэтому \(1\) должен быть элементом \(S\).
- Тенцинг не любит друга \(n\), поэтому \(n\) не должен быть элементом \(S\).
- Существует m дополнительных ограничений. \(i\)-е специальное ограничение описывается целыми числами \(u_i\), \(v_i\) и \(y_i\). Предположим, что \(x\) — это общее время, в течение которого ровно один из \(u_i\) и \(v_i\) играет с Тенцингом. Тенцинг должен гарантировать, что \(x\) меньше или равно \(y_i\). Иначе будет несчастье.
Тенцинг хочет узнать максимальное общее время, которое он может играть со своими друзьями животными. Пожалуйста, найдите максимальное общее время, которое Тенцинг может играть со своими друзьями животными, и способ организации игр, при котором достигается это максимальное общее время, или сообщите, что он может играть со своими друзьями животными бесконечное количество времени. Кроме того, Тенцинг не хочет устраивать очень много игр, поэтому он устроит не более \(n^2\) игр.
Выходные данные
Если Тенцинг может играть со своими друзьями-животными бесконечное количество времени, выведите «inf» (без кавычек).
Иначе, в первой строке выведите общее время \(T\) (\(0 \leq t \leq 10^{18}\)) и количество игр \(k\) (\(0 \leq k \leq n^2\)).
В следующих \(k\) строках вывода выведите двоичную строку \(s\) длины \(n\) и целое число \(t\) (\(0 \leq t \leq 10^{18}\)) — представление множества \(S\) и количество минут, в течение которых будет играться эта игра. Если \(s_i=\texttt{1}\), то \(i \in S\), иначе, если \(s_i=\texttt{0}\), то \(i \notin S\).
При ограничениях этой задачи можно доказать, что если Тенцинг может играть со своими друзьями только конечное количество времени, то он может играть с ними не более \(10^{18}\) минут.
Примечание
В первом примере:
- Тенцинг проведёт игру с другом \(\{1\}\) в течение \(1\) минуты.
- Тенцинг проведёт игру с друзьями \(\{1,4\}\) в течение \(1\) минуты.
- Тенцинг проведёт игру с друзьями \(\{1,3\}\) в течение \(1\) минуты.
- Тенцинг проведёт игру с друзьями \(\{1,2,3,4\}\) в течение \(1\) минуты.
Если после этого Тенцинг проведет еще одну игру с друзьями \(\{1,2\}\) в течение \(1\) минуты, то время пребывания ровно одного из друзей \(2\) или \(3\) с Тенцинг станет \(2\) минуты, что не будет удовлетворять \(3\)-му ограничению.
Во втором наборе никаких специальных ограничений нет. Поэтому Тенцинг может играть с другом \(\{1\}\) в течение бесконечного количества времени.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
1 3 2
1 4 2
2 3 1
2 5 1
|
4 4
10000 1
10010 1
10100 1
11110 1
|
|
2
|
3 0
|
inf
|