У Вадима есть любимое нечётное простое число P. Все вычисления он делает только по модулю P, даже когда этого делать не стоит. Так, на днях он услышал про квадратичные иррациональности. Это числа вида a + b · √c. Само собой, Вадим захотел написать калькулятор, который будет обрабатывать подобные числа. Ваша задача заключается в том, чтобы помочь ему это сделать.

Как известно, в калькулятор вначале вводится одно число, а затем над ним проводятся операции. Вам нужно реализовать 5 операций: сложение, вычитание, умножение и деление квадратичных иррациональностей, а также возведение в степень. Заметьте, что все эти вычисления должны проводиться по модулю P. Если для числа a существуют x₁ и x₂ такие, что x₁² ≡ x₂² ≡ a (mod P), то Вадим считает правильным результатом извлечения корня меньшее из них. Все последующие вычисления будут выполняться, исходя из этого результата. Также Вадим знает, что 0⁰ = 1, поэтому калькулятор обязан считать именно так.

Вадим вас уверяет, что все результаты будут иметь вид a + b · √c, где a, b, c ∈ [0; P − 1], при этом у одного и того же числа может быть несколько представлений. Из всех таких нужно выводить то, у которого c минимально. Если таких несколько, то нужно вывести то, у которого b минимально.

В первой строке даются три целых числа A, B и C — изначальная квадратичная иррациональность A + B · √C (0 ≤ A, B, C ≤ 10⁹).

Во второй строке даются два целых числа Q и P — количество операций на калькуляторе и любимое простое число Вадима (1 ≤ Q ≤ 10⁵, 3 ≤ P ≤ 10⁹ + 9, P — простое).

В следующих Q строках описываются операции в одном из форматов ниже:

Все числа a, b, c и n — целые.

После выполнения каждой операции выведите три целых числа a, b и c, описывающие текущее значение по модулю P. Если есть несколько ответов, выведите тот, у которого c минимально. Если таких ответов несколько, выведите тот, у которого b минимально.