Steganography

Time limit4sMemory limit1024 MB

Summary

Given point-coloring updates and queries, check whether two equal-sized rectangles on the lattice have identical color patterns.

Level: Medium7 of 10
Topics: String matching, Prefix sum, Binary search
Solved: No attempts yet

Problem

MatKor was certified as a cyber defense department club in the second semester, based on its 2022 first-semester activities and the <1st MatKor Cup: 2022 Summer> held in the summer. MatKor now recruits members openly and has started a range of activities, including seminars and projects.

AlKor, another cyber defense department club, plans to keep MatKor in check. Noticing this, Changho, the president of MatKor, decides to hide information using steganography.

Steganography is a technique for secretly hiding other data inside information such as a photo or a message. Read the note below to learn what steganography is in more detail. Changho's steganography method hides information using the colors of lattice points on a two-dimensional coordinate plane. At first, every lattice point has color $0$ . Changho can perform the following two actions.

Hide: paint one given point with a given color.
Check: determine whether the colored patterns in two given two-dimensional ranges are identical.

The colored patterns in the ranges $\left[ x_1,x_1+w \right]\times\left[ y_1,y_1+h \right]$ and $\left[ x_2,x_2+w \right]\times\left[ y_2,y_2+h \right]$ are identical if, for every integer $0\le i\le w$ and $0\le j\le h$ , the color of $(x_1+i,y_1+j)$ equals the color of $(x_2+i,y_2+j)$ .

Given a check action, help Changho determine whether the colored patterns in the two given two-dimensional ranges are identical.

Input

The first line contains the number of actions $Q(1\le Q\le 10^5)$ that Changho performs.

Each of the next $Q$ lines gives one action in one of the following formats.

A hide action is given as 1 $x$ $y$ $c$ . It means point $(x,y)$ is painted with color $c$ .
A check action is given as 2 $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$ $w$ $h$ . It means you must determine whether the colored patterns in the two-dimensional ranges $\left[ x_1,x_1+w \right]\times\left[ y_1,y_1+h \right]$ and $\left[ x_2,x_2+w \right]\times\left[ y_2,y_2+h \right]$ are identical.

All input values are integers from $-10^{9}$ to $10^{9}$ , inclusive. The values $w$ and $h$ are non-negative integers.

At least one check action is given.

Output

For each check action, print 1 if the colored patterns in the two ranges are identical, and 0 otherwise. Print one answer per line.

Hint

Steganography is a technique for hiding data inside other data. It usually embeds very small changes in photos, videos, or music, such as slightly adjusting image pixels or audio frequencies. The changes are hard to notice at a glance, but if the concealment is not careful, the altered parts stand out from the original. Encryption makes the data itself unreadable, while steganography only hides it. An acrostic, where the first letters of each line spell a hidden message, is also a form of steganography.

MatKor has used steganography before. In the photo on the rules tab of the <6th Korea University MatKor Cup: 2025 Winter> contest, and in a problem from the <1st MatDegy Cup>, participants had to find a hidden problem.

Free tools for simple steganography are publicly available, and a web search for steganography encoding or decoding turns up many of them. For example, you can use a free tool.

Examples2

Example 1
Input
```
3
1 1 1 1
1 3 1 1
2 1 1 3 1 1 1
```
Expected output
```
1
```

Example 2

Input

9
1 2 3 4
1 3 4 5
1 4 5 4
1 12 13 4
1 13 14 5
1 14 15 4
2 2 3 3 4 1 1
2 2 3 12 13 2 2
2 100 100 100 100 100 100

Expected output

0
1
1