Majority Flavor

In Coffee's world, lollipops come in various flavors. Coffee has bought \(n\) consecutive lollipops, numbered from \(1\) to \(n\). Each lollipop \(i\) has a flavor denoted by \(c_i\). Two lollipops \(i\) and \(j\) share the same flavor if and only if \(c_i = c_j\).

For any segment of these lollipops defined by indices \(s\) to \(t\) (inclusive), Coffee defines the overall flavor as follows: if there exists a flavor \(c_0\) whose occurrence is strictly greater than half of the total lollipops in the segment (i.e., more than \((t-s+1)/2\)), then the overall flavor is \(c_0\). Otherwise, the segment is considered mixed.

You are given \(m\) queries. The \(i\)th query specifies a segment from \(s_i\) to \(t_i\). Determine the overall flavor of each segment.

Note: If a majority flavor exists in a segment, it is guaranteed to be unique.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5)\) --- the number of lollipops and the number of queries.

The second line contains \(n\) strings \(c_1, c_2, \ldots, c_n\) representing the flavors of the lollipops.

Each of the following \(m\) lines contains two integers \(s_i\) and \(t_i\) \( (1 \leq s_i \leq t_i \leq n)\) --- the start and end indices of the \(i\)th query.

outputFormat

For each query, output the overall flavor of the segment in a separate line. If no flavor appears more than half the times in the segment, output mixed (without quotes).

sample

5 3
a b a c a
1 3
2 4
1 5

a
mixed
a