Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Спец (скраћено од специфична) вредност низа се рачуна као производ свих елемената низа подељен са бројем елемената тог низа. Нпр. спец вредност низа \([5, 9, 7]\) je \(\frac{5 \cdot 9 \cdot 7}{3} = 105\).

Спец X-0-1-трансформација низа трансформише низ тако што сваки елемент који није \(0\) или \(X\) постаје \(1\). Нпр. спец 3-0-1-трансформација низа \([4, 3, 2, 0, 3, 1, 0, 5]\) ће трансформисати овај низ у: \([1, 3, 1, 0, 3, 1, 0, 1]\).

Спец L-R-одсецање низа се ради тако што из низа избришемо све елементе чији је индекс мањи од \(L\) или већи од \(R\) (рачунамо да индексирање почиње од \(0\), и \(L \leq R\)). Нпр. након спец 2-5-одсецања низа \([3, 6, 2, 5, 3, 10, 0, 4]\) ће остати низ \([2, 5, 3, 10]\).

Дат вам је низ \(А\) који се састоји од \(N\) целих бројева. Потребно је одговорити на \(Q\) упита, где се сваки упит састоји од једног броја \(Q_i\). За сваки упит је потребно пронаћи бројеве \(L\) и \(R\) за које је спец вредност низа највећа могућа након што се над почетним датим низом уради спец \(Q_i\)-0-1-трансформација и спец L-R-одсецање. Уколико постоји више могућих решења, изабрати оно где је \(L\) најмање, уколико и даље постоји више решења изабрати оно где је \(R\) најмање.

Опис улаза

Прва линија улаза садржи два броја, број елемената низа \(N\), и број упита \(Q\). Друга линија улаза садржи низ \(A\) од \(N\) бројева. У наредних \(Q\) линија улаза се налази по један број \(Q_i\).

Опис излаза

На стандардни излаз исписати \(Q\) линија, тако да у \(i\)-тој линији буду исписана два броја, \(L\) и \(R\), одвојена размаком, који су одговор на упит \(Q_i\).

Пример 1

Улаз

16 7
4 1 4 5 2 2 3 3 2 3 5 0 5 4 4 2
5
3
2
1
4
6
3

Излаз

3 3
6 9
4 4
0 0
13 14
0 0
6 9

Објашњење примера

Уколико посматрамо пети упит, где је \(Q_i = 4\), након спец 4-0-1-трансформације низ ће нам бити \([4,1,4,1,1,1,1,1,1,1,1,0,1,4,4,1]\), па је најбоље одрадити спец 13-14 одсецање како би нам остао низ \([4,4]\) чија је спец вредност \(8\) што је највеће могуће. Уколико посматрамо трећи упит, где је \(Q_i = 2\), након спец 2-0-1-трансформације низ ће нам бити \([1,1,1,1,2,2,1,1,2,1,1,0,1,1,1,2]\). Највећу спец вредност коју можемо добити након одсецања је 2 што се може добити са више различитих одсецања (нпр. за \(L=15\), \(R=15\) или \(L=4\),\(R=5\) или \(L=4\),\(R=4\)), али по условима задатка треба исписати \(L=4\) и \(R=4\). У четвртом и шестом упиту, где је \(Q_i = 1\) i \(Q_i = 6\), након спец трансформације низ ће бити \([1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1]\).

Ограничења

Тест примери су подељени у 5 подзадатка: