Dynamic Modular Equation System Queries

You are given \(N\) variables \(x_1, x_2, \dots, x_N\) and a constant \(K\). Initially, you are given \(M\) equations of the form \(x_a - x_b \equiv c \pmod{K}\). Then you will process \(Q\) operations. Each operation is one of the following:

• Add Equation: 1 a b c — add the equation \(x_a - x_b \equiv c \pmod{K}\).
• Remove Equation: 2 a b — remove the equation between \(x_a\) and \(x_b\) (if it exists).
• Query: 3 a c b — set \(x_a = c\) and determine \(x_b \bmod K\) based on the current equations. If \(x_b\) cannot be uniquely determined, output \(-1\).

It is guaranteed that at any moment there is at most one equation between any two variables, the system is always consistent, and no redundant conditions exist (i.e. an equation can be deduced from others) unless explicitly added.

inputFormat

The first line contains four integers: (N), (K), (M), (Q).

The next (M) lines each contain three integers a b c, representing an equation (x_a - x_b \equiv c \pmod{K}).

The following (Q) lines each describe an operation in one of the following formats: • 1 a b c — add an equation (x_a - x_b \equiv c \pmod{K}). • 2 a b — remove the equation between (x_a) and (x_b). • 3 a c b — query: assign (x_a = c) and output (x_b \bmod K) or (-1) if undetermined.

outputFormat

For each query operation (lines beginning with 3), output a single integer on a new line: the computed value of (x_b \bmod K), or (-1) if it cannot be determined.

sample

3 7 2 5
1 2 3
2 3 4
3 1 0 3
1 1 3 0
3 2 1 3
2 2 3
3 1 2 3

0
4
2