Артём поехал на море и хочет привести двум своим сокомандникам сувениры. На главной туристической улице города есть n магазинов. В i-м магазине Артём может купить один сувенир за a_i рублей, покупать больше одного сувенира в одном магазине нельзя. Артём не хочет сеять зависть в своей команде, поэтому цена двух сувениров, которые он привезёт друзьям, должна отличаться как можно меньше.

Артём заходил на улицу с магазинчиками m раз. По неизвестной причине в его i-й визит работали только магазины с номерами с l_i по r_i (бред? да, но вы сами когда-нибудь пытались придумать вразумительную легенду к задаче про запросы на отрезках?). Для каждого визита Артём хочет узнать минимальную возможную разность между ценой сувениров, которые он может купить в открытых магазинах.

Другими словами, для каждого раза, когда Артём заходил на улицу, найдите минимально возможное значение |a_s - a_t|, где l_i ≤ s, t ≤ r_i, s ≠ t.