Сравнение разбиений результатов забега

После школьского забега результаты спортсменов собраны в первой таблице. Время указано в миллисекундах. Если секундомер не сохранил результат спортсмена, вместо времени записан символ -.

Во второй таблице приведены два готовых варианта разбиения спортсменов на группы. Строки второй таблицы могут идти в другом порядке, поэтому результаты и номера групп необходимо сопоставлять по идентификатору спортсмена.

Для каждого разбиения вычисляется инерция. Спортсмены с пропущенным временем в вычислении не участвуют. Для каждой группы с временами $x_1, x_2, \dots, x_k$ её среднее время равно $\mu = (x_1 + x_2 + \dots + x_k) / k$, а вклад группы в инерцию равен $\sum_{i=1}^{k}(x_i-\mu)^2$. Инерция разбиения равна сумме вкладов всех его групп.

Требуется вывести номер разбиения с меньшей инерцией: 1 или 2. Гарантируется, что после исключения пропущенных результатов в каждом разбиении каждая встречающаяся группа содержит хотя бы одного спортсмена.

При равенстве инерций следует вывести 1.

Выводится целое число, округление не требуется.

Формат ввода

В первой строке записано целое число n — число спортсменов.

В следующих n строках записаны идентификатор спортсмена id и его время time. Значение time равно целому числу миллисекунд или символу -.

В следующих n строках записаны идентификатор спортсмена id, номер его группы в первом разбиении group1 и номер его группы во втором разбиении group2.

Каждый идентификатор из первой таблицы встречается во второй таблице ровно один раз.

Формат вывода

Выведите 1, если инерция первого разбиения не больше инерции второго разбиения. Иначе выведите 2.

Ограничения

$1 \le n \le 2000$.

Длина каждого идентификатора составляет от 1 до 20 символов. Идентификаторы состоят из латинских букв, цифр и символа _.

Если время не пропущено, то $1 \le time \le 1000000$.

$1 \le group1, group2 \le n$.

Хотя бы у одного спортсмена время не пропущено. После исключения спортсменов с time = - каждая группа, встречающаяся в любом из двух разбиений, непуста.