У ослика Иа-Иа сегодня день рождения. Его друг, Винни-Пух, хочет сделать ему самый лучший подарок — горшочек меда. Конечно, медвежонок понимает, что полный горшочек до ослика донести не удастся, потому что по пути он съест весь мед. А раз уж Винни собрался перекусить по пути, то изначально в горшочке должно быть как можно больше меда.
За день до этого Винни-Пух пополнил свои запасы меда. Дома у Винни-Пуха есть n полок, на каждой из которых находится некоторое, возможно нулевое, количество горшочков с медом. В течение дня Винни q раз подходил к полкам с медом; в i-тый раз он подходил к некоторой полке ui, брал с нее некоторое количество горшочков ki, пробовал мед из каждого из них и ставил все эти горшочки на некоторую полку vi. Выбирая горшочки, Винни руководствовался интуицией, а, значит, можно считать, что среди всех наборов из ki горшочков на полке ui, он равновероятно выбирает один.
Сейчас Винни помнит все действия, которые он выполнял с горшочками меда. На праздник он хочет взять горшочек, который вчера ему не попадался. Для этого ему необходимо знать математическое ожидание m количества полок, на которых нет ни одного нетронутого медвежонком горшочка. Для того, чтобы лучше оценить свои шансы, Винни-Пух хочет знать значение m после каждого выполненного им действия.
Ваша задача — написать программу, которая найдет эти значения за него.