Vadim has a favorite odd prime number P. He does all calculations only modulo P, even when he should not. Recently, he heard about quadratic irrationals. These are numbers of the form a + b · √c. Naturally, Vadim wanted to write a calculator that can process such numbers. Your task is to help him do that.

As is known, a calculator first receives one number, and then operations are performed on it. You need to implement 5 operations: addition, subtraction, multiplication, and division of quadratic irrationals, as well as exponentiation. Note that all these calculations must be performed modulo P. If for a number a there are x₁ and x₂ such that x₁² ≡ x₂² ≡ a (mod P), then Vadim considers the smaller of them to be the correct square root. All subsequent calculations will be performed based on this result. Vadim also knows that 0⁰ = 1, so the calculator must compute exactly this.

Vadim assures you that all results will have the form a + b · √c, where a, b, c ∈ [0; P − 1], and the same number may have several representations. Among all such representations, you must output the one with the smallest c. If there are several such representations, output the one with the smallest b.

The first line contains three integers A, B, and C — the initial quadratic irrational A + B · √C (0 ≤ A, B, C ≤ 10⁹).

The second line contains two integers Q and P — the number of operations on the calculator and Vadim’s favorite prime number (1 ≤ Q ≤ 10⁵, 3 ≤ P ≤ 10⁹ + 9, P is prime).

The next Q lines describe operations in one of the following formats:

All numbers a, b, c, and n are integers.

After each operation, print three integers a, b, and c describing the current value modulo P. If there are several answers, print the one with the smallest c. If there are several such representations, print the one with the smallest b.