Purification Challenge

You are given a sequence of n pairs, where each pair represents a magic talisman with a color and an amount of impurity attached to it. The pair is denoted as \((c_i, a_i)\) where \(c_i\) is the color and \(a_i\) is the impurity level.

There are \(q\) queries. Each query provides an interval \([l, r]\) (1-indexed) and requires you to compute the value:

[ \max_{k=1}^{n} \left{ \min_{l \le i \le r, ; c_i = k} a_i \right} ]

For each color \(k\) not present in the interval \([l,r]\), the minimum is defined as \(0\). In other words, for every query, you need to group the talismans in the interval by color, take the minimum impurity level for each color, and then output the maximum value among these minimums.

Note: The queries do not modify the sequence.

inputFormat

The first line contains two integers \(n\) and \(q\) denoting the number of talismans and the number of queries.\

The next \(n\) lines each contain two integers \(c_i\) and \(a_i\) representing the color and impurity level of the \(i\)-th talisman.

Each of the next \(q\) lines contains two integers \(l\) and \(r\), representing the interval (1-indexed) for the query.

outputFormat

For each query, output one line with a single integer: the required maximum value among the minimum impurity levels computed for each color in the interval.

sample

5 3
1 5
2 3
1 2
2 4
3 6
1 3
2 5
1 5

3
6
6