Давным-давно существовало великое королевство, которым правили Великий Арий и Пари Великая. У этих двоих были некоторые разногласия по вопросу любимых чисел, поэтому они решили разделить королевство между собой.
Великое королевство состояло из n городов, пронумерованных целыми числами от 1 до n, и m двунаправленных дорог, пронумерованных от 1 до m. Длина i-й из этих дорог равняется wi. Великий Арий и Пари Великая договорились уничтожить некоторый префикс дорог (все дороги с номером меньше некоторого x) и некоторый суффикс дорог (все дороги с номером больше некоторого x), оставив таким образом дороги с номерами l, l + 1, ..., r - 1 и r.
После этого они разделят королевство на две части (каждый город отойдёт ровно к одной из двух частей), такие что трудность разделения будет минимальна. Трудностью разделения называется максимальная длина дороги, такой что оба её конца принадлежат одной части. В случае если таких дорог вообще нет, трудность разделения полагается равной - 1.
Историки обнаружили карту великого королевства и теперь обсуждают q возможных сценариев выбора параметров l и r великими правителями. По имеющимся данным для каждой гипотезы li, ri определите минимально возможную трудность разделения королевства.