Background

The Ancient God Segment Tree is too hard, and the problem setter could not solve it, so they modified it.

Problem Description

• A line is represented as $(sx, sy, tx, ty)$, and it is guaranteed that $sx \not= tx$.
• When a line appears, it lights up all integer points $(x, y)$ that satisfy:$$y \cdot (tx-sx) \cdot \big( (ty-sy)\cdot(x-sx) - (tx-sx)\cdot(y-sy) \big) \ge 0$$
• A point that has already been lit will not be turned off, and will not be lit a second time.

There are $n$ operations. An operation can be:

1. Add a line.
2. Query the number of lit points in a rectangular region.

Each test point contains multiple groups of testdata.

Input Format

The first line contains two positive integers $c, T$, representing the test point ID and the number of testdata groups. In the sample, $c$ is the smallest test point ID that satisfies the corresponding property.

For each group of testdata:

• The first line contains one positive integer $n$, representing the number of operations.

• The next $n$ lines each contain $5$ integers, describing an operation as follows:

  • 1 sx sy tx ty: add a line.
  • 2 lx ly rx ry: query the number of lit points satisfying $lx{\le}x{\le}rx$ and $ly{\le}y{\le}ry$.

Output Format

For each operation $2$, output one number per line as the answer.

1 1
3
1 1 2 4 1
1 4 4 2 1
2 1 1 4 3

8

Hint

The input size of this problem is large. A fast input template is provided in the downloadable files.

For all data:

• $1 \le n \le 1\times 10^6$.
• $1 \le \sum n \le 2\times 10^6$.
• $-10^9 \le sx, sy, tx, ty \le 10^9$, and $sx \not= tx$.
• $-10^9 \le lx \le rx \le 10^9$, $-10^9 \le ly \le ry \le 10^9$.

::cute-table{tuack}

• Special Property A: It is guaranteed that $\lvert lx \rvert, \lvert rx \rvert, \lvert ly \rvert, \lvert ry \rvert \le 500$.
• Special Property B: It is guaranteed that $lx = rx$.
• Special Property C: It is guaranteed that $sx = 0, sy = 0$.
• Special Property D: It is guaranteed that $ly = -1e9, ry = 1e9$.

Translated by ChatGPT 5