Hypercube Intersection Volume

You are given n operations related to positive k-dimensional hypercubes. There are two types of operations:

• Operation 1: Add a positive k-dimensional hypercube. The hypercube is defined as \([0, a]^k\), where a is its side length.
• Operation 2: Given a positive k-dimensional hypercube \([0, a]^k\), compute the volume of the intersection between the union of all previously added hypercubes (of the same dimension k) and this query hypercube, and output the answer modulo \(1919810\). If no hypercube of that dimension exists, the answer is 0.

Note: Since each added hypercube has one corner at the origin and extends to \(a\) along every axis, the union of hypercubes in the same dimension is simply \([0, M]^k\), where \(M\) is the maximum side length among them. Therefore, the answer for an operation 2 is \(\min(M, a)^k \bmod 1919810\) (with \(x^k\) being the volume of a \(k\)-dimensional hypercube \([0, x]^k\)).

inputFormat

The first line contains an integer n, the number of operations. Each of the following n lines describes an operation in the format:

type k a

Where type is either 1 or 2. For an operation of type 1, add the hypercube \([0, a]^k\). For an operation of type 2, query the volume of the intersection between the union of all added hypercubes (of dimension k) and the query hypercube \([0, a]^k\), then output the answer modulo \(1919810\).

outputFormat

For each operation of type 2, output the result on a separate line.

sample

5
1 2 3
2 2 5
1 2 10
2 2 7
2 3 5

9
49
0