У Републици Изометрији највећи годишњи спекаткл је велика трка која се одржава у срцу државе - Централграду. Ту долазе најбољи тркачи и најспремнији рекреативци из свих већих градова државе и боре се за титулу Високог Велемајстора Метрика.

Централград има облик дводимензионог координатног система. Трака трке је одређена стартном тачком и са \(k\) стубова на следећи начин: у \(i\)-том делу трке тркачи трче од тренутне позиције до \(i\)-тог стуба, али кад стигну до њега наставе да трче у истом правцу и смеру тако да пређу још толику дистанцу колико су прешли до тад у том делу трке, то јест \(i\)-ти стуб треба да буде средиште дужи која спаја почетак и крај \(i\)-тог дела трке. Другим речима, завршетак \(i\)-тог дела трке (и почетак \(i+1\)-вог дела) је тачка централно симетрична у односу на \(i\)-ти стуб.

Организатори су поставили \(N\) стубова нумерисаних са \(1,2,\ldots,N\), али нису још одредили које ће користити у трци. Због тога желе да разраде \(Q\) сценарија, где је \(i\)-ти сценарио одређен са четири вредности: \(x\) и \(y\) које представљају координате почетка трке и \(L\) и \(R\) које представљају да ће за трку бити искоришћени редом стубови нумерисани са \(L,L+1,\ldots,R\). Организатори су мало смотани, па траже од вас да одредите за сваки сценарио где би се налазио крај трке. ## Опис улаза У првом реду улаза се налази природан број \(N\)-број стубова. У наредних \(N\) редова се налазе по \(2\) природна бројевa \(x_i\) и \(y_i\) које представљају локације постављених стубова. У наредном реду се налази природан број \(Q\)-број сценарија. У наредних \(Q\) линија се налази по четири броја \(x,y,L,R\) којим су описани сценарији. ## Опис излаза На излаз исписати \(Q\) редова са по \(2\) броја, где бројеви у \(i\)-том реду представљају координате циља у \(i\)-том сценарију. ## Ограничења

• \(1 \leq N,Q \leq 200.000\)
• \(0\le x_i,y_i\le10^9\)
• \(0\le x ,y\le10^9\) за сваки упит
• \(1\le L\le R\le N\) за сваки упит

Тест примери су подељени у 4 дисјунктне групе:

• У тест примерима вредним \(10\) поена: \(N,Q\leq 1000\), \(x_i,y_i\le 1.000.000\) и \(x,y\le 1.000.000\) за сваки упит.
• У тест примерима вредним \(10\) поена: Kоординате свих стубова су исте.
• У тест примерима вредним \(30\) поена: \(y\) координате свих стубова и стартова су једнаке \(0\)
• У тест примерима вредним \(50\) поена: Без додатних ограничења.

Примери

Пример 1

Улаз

2
1 1
3 3
2
0 0 1 1
0 0 1 2

Излаз

2 2
4 4

Објашњење

У првом сценарију, трка има само један део који води од \((0,0)\) до \((2,2)\), јер је \((1,1)\) средиште те дужи. У другом сценарију, трка има два дела, први води од \((0,0)\) до \((2,2)\), као у првом сценарију, а други води од \((2,2)\) до \((4,4)\).