Когда у Таи заканчиваются деньги, она идет в казино. Недавно в казино появилась новая игра, и Тая хочет освоить её. Помогите ей.

В игре участвуют две стороны: крупье и посетитель казино. У крупье есть одна обычная $k$-гранная кость, на гранях которой написаны все целые числа от 1 до $k$. Крупье начинает игру, бросая кость один раз. Выпавшее число определяет количество очков, набранных крупье.

Чтобы выиграть, посетитель должен набрать больше очков, чем крупье. Для этого предлагается выбор из $n$ вариантов. Каждый вариант представляет собой пару: кость и количество разрешенных бросков. На каждой грани каждой кости написано некоторое число. Эта кость бросается требуемое количество раз, все выпавшие числа суммируются, и эта сумма составляет количество очков, набранных посетителем.

Однако некоторые грани, помимо чисел, имеют бонусные отметки. Если на выпавшей грани есть бонусная отметка, то соответствующее количество очков добавляется к общей сумме, и посетитель получает дополнительный бросок кости. Все грани одной кости попарно различны, что означает, что нет двух одинаковых бонусных граней и нет двух одинаковых обычных граней. Каждая кость имеет как минимум одну грань без бонусной отметки. Для каждой кости вероятность выпадения любой из её граней одинакова.

В этой задаче требуется для каждого возможного количества очков крупье от 1 до $k$ определить номер варианта броска посетителя, который приводит к максимальной вероятности набрать строго больше очков, чем набрал крупье.

Входные данные

Первая строка входных данных содержит единственное целое число $n$ ($2 \le n \le 10$) — количество вариантов броска костей.

Следующие $n$ строк содержат описания вариантов в следующем формате: Первое число $c_i$ ($1 \le c_i \le 10$) — количество разрешенных бросков. Второе число $f_i$ ($2 \le f_i \le 12$) — количество граней кости. Далее следуют $f_i$ чисел $v_{ij}$ — числа, написанные на гранях. $v_{ij}$ — это либо просто число от 1 до $f_i$, означающее количество очков, либо оно может иметь дополнительный знак «+» (ASCII 43) перед числом, который является бонусной отметкой. Для каждой кости числа без знака «+» уникальны, все числа со знаком «+» уникальны, и есть как минимум одна грань без бонусной отметки.

Последняя строка содержит единственное целое число $k$, которое всегда равно $\max_{1 \le i \le n} (c_i \times f_i)$.

Выходные данные

Выходные данные должны содержать $k$ строк, каждая из которых содержит единственное целое число $b_i$ — номер лучшего варианта, который позволит выиграть с максимальной вероятностью, набрав больше $i$ очков (эта вероятность не должна отклоняться от правильного ответа более чем на $10^{-9}$).

Кости нумеруются от 1 в порядке их появления во входных данных.

Примеры

Входные данные 1

3
3 4 1 2 3 4
2 6 1 2 3 4 5 6
1 12 1 2 3 4 5 6 7 8 9 10 11 12
12

Выходные данные 1

2
1
1
1
1
1
1
3
3
3
3
2

Входные данные 2

2
1 4 1 2 +1 +2
1 6 1 +1 2 3 4 5
6

Выходные данные 2

2
2
2
2
1
1

Примечание

Ответ для первого примера может содержать 1 в первой строке, а последняя может быть любой от 1 до 3.