Артём поехал на море и хочет привести двум своим сокомандникам сувениры. На главной туристической улице города есть n магазинов. В i-м магазине Артём может купить один сувенир за ai рублей, покупать больше одного сувенира в одном магазине нельзя. Артём не хочет сеять зависть в своей команде, поэтому цена двух сувениров, которые он привезёт друзьям, должна отличаться как можно меньше.
Артём заходил на улицу с магазинчиками m раз. По неизвестной причине в его i-й визит работали только магазины с номерами с li по ri (бред? да, но вы сами когда-нибудь пытались придумать вразумительную легенду к задаче про запросы на отрезках?). Для каждого визита Артём хочет узнать минимальную возможную разность между ценой сувениров, которые он может купить в открытых магазинах.
Другими словами, для каждого раза, когда Артём заходил на улицу, найдите минимально возможное значение |as - at|, где li ≤ s, t ≤ ri, s ≠ t.