Professional Fence Decorator

Vasya is an apprentice at a well-known studio. He was recently assigned to help Vitezslav Smolokurov, a young fence decorator with great promise. The task is very important, and Vasya's future depends on how it goes.

Smolokurov's style is highly unusual, and his work is in great demand. The job has two stages. In the first stage, Vasya makes a blank: a long fence made of a row of colored vertical slats. In the second stage, Vitezslav starts working.

To give the fence a calmer, more harmonious look, he repeats the following operation several times: he picks a color and a segment, then repaints that segment in the chosen color. Smolokurov is creative and may change the design completely several times an hour, so he sometimes repaints the same slat more than once. He also does not want any pattern to repeat too often, so he sometimes checks whether one segment of the fence matches another.

Vasya does the repainting and the checking. The work is not easy, so Vasya asks for help, at least with the match checks.

The first line contains one integer $n$, the number of slats in the fence ($1 \le n \le 100\,000$). The second line contains $n$ integers separated by spaces, the colors of the slats.

The third line contains one integer $m$, the number of comparison and repaint tasks ($1 \le m \le 100\,000$). Each of the next $m$ lines contains four integers $q$, $l$, $r$, and $k$.

For a repaint, $q = 0$. It means repainting all slats from $l$ to $r$ inclusive to color $k$ ($1 \le l \le r \le n$). For a comparison, $q = 1$. It means comparing the fence pieces of length $k$ that start at positions $l$ and $r$ ($1 \le l, r \le n - k + 1$, $k > 0$).

All numbers in the input are positive and do not exceed $100\,000$.

Output one line. For each comparison query, print <<+>> if the two pieces match and <<->> otherwise.