Toy Shop Promotions

Frezz owns a toy shop in City C which offers n kinds of toys, numbered from 1 to n. The i-th toy has an initial unit price \(c_i\) (in yuan) and provides a pleasure value \(v_i\). At various times, m children (the i-th child always bringing \(i\) yuan) visit the shop and purchase any number of toys from a specified interval.

The shop also experiences changes over time. There are \(Q\) events, each described by parameters \(op, l, r\) where \(op\) is an integer in \(\{1,2,3\}\) with the following meanings:

• Price Adjustment (\(op=1\)): An extra parameter \(d\) is given. For every toy with index \(i\) in the interval \([l,r]\), update its price as follows: \[ c_i \leftarrow c_i + d, \quad\text{and if } c_i > m \text{ then } c_i \leftarrow c_i - m. \] (d is a positive integer not exceeding \(m\)).
• Pleasure Adjustment (\(op=2\)): An extra parameter \(b\) (which may be negative) is given. For every toy with index \(i\) in \([l,r]\), update its pleasure: \[ v_i \leftarrow v_i + b. \]
• Purchase Event (\(op=3\)): All \(m\) children visit the shop and are allowed to buy an arbitrary nonnegative number of copies of each toy in the index range \([l,r]\). For each child, with budget equal to the money he brings, they choose a purchasing strategy to maximize his individual total pleasure. Let \(f(x)\) denote the maximum pleasure that can be obtained with a budget of \(x\) (using toys in the interval and each toy available in unlimited quantity, i.e. a complete knapSack problem). You are to answer two questions for every purchase event:
  1. The sum of the maximum pleasures over all children, i.e. \(\sum_{i=1}^{m} f(i)\).
  2. The XOR (using the \(xor\) or \(\oplus\) operator) of the maximum pleasures across all children, i.e. \(f(1) \oplus f(2) \oplus \dots \oplus f(m)\).

Input Format:

The first line contains three integers \(n, m, Q\). The second line contains \(n\) integers \(c_1, c_2, \dots, c_n\) representing the initial prices. The third line contains \(n\) integers \(v_1, v_2, \dots, v_n\) for the initial pleasure values. Then, there are \(Q\) lines each describing an event. For an event:

• If \(op=1\), the line contains: 1 l r d.
• If \(op=2\), the line contains: 2 l r b.
• If \(op=3\), the line contains: 3 l r.

Output Format:

For each purchase event (\(op=3\)), output a single line with two space‐separated numbers: the sum \(\sum_{i=1}^{m} f(i)\) and the XOR \(f(1) \oplus f(2) \oplus \dots \oplus f(m)\).

inputFormat

The first line contains three integers \(n\), \(m\) and \(Q\).
The second line contains \(n\) integers \(c_1,c_2,\dots,c_n\) -- the initial prices of the toys.
The third line contains \(n\) integers \(v_1,v_2,\dots,v_n\) -- the initial pleasure values of the toys.
Then \(Q\) lines follow, each describing an event:

• For a price adjustment event (\(op=1\)): 1 l r d.
• For a pleasure adjustment event (\(op=2\)): 2 l r b.
• For a purchase event (\(op=3\)): 3 l r.

It is guaranteed that \(1 \leq l \leq r \leq n\) and for \(op=1\), \(d\) is a positive integer not exceeding \(m\); for \(op=2\), \(b\) is an integer (possibly negative).

outputFormat

For each purchase event, output one line with two integers: the maximum total pleasure sum from all children and the XOR of maximum pleasures, separated by a space.

sample

3 3 5
1 2 3
1 2 3
3 1 3
1 1 2 1
3 2 3
2 3 3 -1
3 1 3

6 0
3 3
6 0