Background

“Because the history and growth of humankind is the history and growth of war. Without conflict, there is no growth. Being satisfied with the status quo means that humans give up survival. The people of the Moon think about the people of the Earth every day. The history of the Earth is created by the people of the Moon.”

“I know the people of the Moon pretty well. Let me put it this way: among residents of all kinds of other worlds, they are the worst type. Extremely exclusive, extremely lacking in freedom, a fabricated paradise. They are good at looking down on others, but they cannot stand being treated like fools. They even think that residents of other worlds are not even as good as germs.”

“The most important problem is that the people of the Moon are hostile to Gensokyo. That’s how it is.”

“I didn’t expect they would send Earthlings to the Moon. I never had such a thought before. Those Moon people who can’t tolerate even a grain of sand in their eyes actually used such a low-class method.”

“Gensokyo was kidnapped as a hostage. You can think of it that way. If you want to save Gensokyo, then you are not allowed to attack the Lunar Capital. That is this inhumane strategy.”

Across a journey of $380{,}000$ kilometers, by the sea that reflects the home star, defeat the irreconcilable enemy, and shatter the eternal dream that never wakes.

不倶戴天の敵、$\stackrel{じょうが}{嫦娥}$よ。見てるか！？
Irreconcilable enemy, Chang’e. Are you watching!?

Problem Description

Brief statement

You are given a sequence of length $n$. Each element is a pair $(c_i,a_i)$, representing its color and weight.

There are $q$ queries. Each query gives an interval $[l,r]$. Compute:

$$\max\limits_{k=1}^n \left\{\min\limits_{l\le i \le r,c_i=k} a_i\right\}$$

In particular, if there is no element of color $k$ in $[l,r]$, then the inner part is defined as $0$.

Original statement

Junko’s ability is purification. Once the filth on Reimu is purified, she will surely die.

Reimu carries $n$ spell cards lined up in a row to transfer filth, but Junko can still purify the filth attached to them and kill Reimu.

Specifically, each time Junko hits all spell cards in an interval $[l_i,r_i]$, Reimu needs to purify the filth on these spell cards before that.
Each spell card has a fixed color $c_i$. After the fierce battle, each spell card is stained with $a_i$ units of filth.
Spell cards of the same color interact with each other. When purifying a batch of spell cards of the same color inside the interval, the spiritual power cost is the minimum filth value among these spell cards.
Because leaked spiritual power can be absorbed by other spell cards, Reimu only needs to know the maximum purification cost among all colors in the interval. This is the spiritual power cost for her to purify once.

Given $\{c_i\}$ and $\{a_i\}$, each time you are given one possible attack $l_i,r_i$ by Junko. Ask for Reimu’s spiritual power cost to purify once. Note that this is only a calculation: after outputting each answer, $\{c_i\}$ and $\{a_i\}$ do not change.

Input Format

The first line contains two integers $n,q$, the length of the sequence and the number of queries.

The second line contains $n$ integers: $c_1,c_2,\cdots,c_n$.

The third line contains $n$ integers: $a_1,a_2,\cdots,a_n$.

The next $q$ lines each contain two integers $l,r$, the interval of each query.

Output Format

Output $q$ lines. Each line contains one integer, the answer to the corresponding query.

10 10
3 2 2 1 2 1 3 2 1 2 
10 4 10 4 9 8 1 4 9 4 
3 4
3 9
4 8
3 6
3 3
9 10
5 8
5 8
6 8
5 8

10
4
4
9
10
9
8
8
8
8

Hint

Explanation for Sample 1

As shown, the numbers represent weights, and the background colors represent colors.

• For interval $[3,4]$, the minimum weights for the two appearing colors are $10$ and $4$. Taking the maximum gives $10$.
• For interval $[3,9]$, the minimum weights for the three appearing colors are $1$, $4$, and $4$. Taking the maximum gives $4$.
• For interval $[4,8]$, the minimum weights for the three appearing colors are $1$, $4$, and $4$. Taking the maximum gives $4$.
• For interval $[3,6]$, the minimum weights for the two appearing colors are $9$ and $4$. Taking the maximum gives $9$.
• For interval $[3,3]$, the minimum weight for the only appearing color is $10$. The rest are similar.

Constraints and notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{n\le } & \bm{q\le} & \textbf{Special property} & \textbf{Subtask dependency} & \textbf{Score}\\\hline 1 & 100 & 100 & - & - & 10\\\hline 2 & 2 \times 10^5 & 2\times 10^5 & \textbf A & - & 20\\\hline 3 & 2 \times 10^5 & 2\times 10^5 & - & 2 & 30\\\hline 4 & 2 \times 10^5 & 10^6 & - & 1,3 & 40\\\hline \end{array}$$

Special property $\textbf A$: all $c_i \leq 10$.

For all testdata, it is guaranteed that $1 \leq n \leq 2\times10^5$, $1 \leq q \leq 10^6$, $1 \le c_i,a_i \le n$, and $l \leq r$.

Translated by ChatGPT 5