Программист Ростислав серьёзно увлёкся структурой данных Link/Cut Tree, которая основана на Splay-деревьях. В частности, сейчас он изучает процедуру expose.

К сожалению, понять определение этой процедуры Ростислав не в состоянии, и поэтому он решил обратиться за помощью к программисту Серёже. Тот согласился помочь, только если Ростислав решит простую задачу (а если не решит, то зачем ему Splay-деревья?)

По заданным l, r и k необходимо вывести все степени числа k в промежутке от l до r, включая границы. Однако Ростиславу не хочется решать эту задачу самостоятельно, ведь он увлекся сетевой игрой в Agar с Глебом. Помогите ему!