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

У каждого грибовода есть свой гриб, который он будет выращивать на состязании. По новым правилам состязание будет состоять из двух частей. Первая часть длится t₁ секунд, а вторая t₂ секунд, между первой и второй частью есть небольшой перерыв.

После стартового свистка начинается первая часть состязания, и все грибоводы одновременно начинают выращивать грибы, каждый со своей скоростью v_i метров в секунду. Спустя t₁ секунд, грибоводы прекращают выращивать грибы и уходят на перерыв. Во время перерыва, по необъяснимым причинам, рост всех грибов уменьшается на k процентов. После перерыва стартует вторая часть состязания и все грибоводы одновременно продолжают выращивать грибы, каждый со своей скоростью u_i метров в секунду. Спустя t₂ секунд после окончания перерыва состязание заканчивается. Обратите внимание, что скорости до перерыва и после перерыва могут отличаться.

Перед состязанием гном Паша узнал у всех участников, какие две скорости они выбрали. Но участники, не захотели раскрывать ему всю свою стратегию и поэтому не сказали в каком порядке они будут использовать эти скорости. То есть если участник выбрал скорости a_i и b_i, то возможны два варианта: либо до перерыва он использует скорость a_i, а после b_i, либо наоборот.

Гном Паша очень хочет выиграть тотализатор. Он знает, что каждый участник выберет стратегию максимизирующую высоту своего гриба. Помогите гному Паше составить финальную таблицу результатов соревнования.

Участники сортируются в таблице результатов по высоте гриба (участники с более высокими грибами стоят в таблице раньше). При равенстве высот грибов участники сортируются по их номеру (участники с меньшим номером стоят раньше).