Прошло је време игре, уживања и разоноде. Прошло је време малих матрица. Данас су рачунари невероватно брзи и могу извршити и до \(10^{100}\) команди у секунди. Из тог разлога комисија вам је спремила једноставан задатак са једном матрицом и много интересантних упита.

У овом задатку вам је дата матрица \(A\) димензије \(n \times m\) - матрица има тачно \(n\) врста и тачно \(m\) колона. Врсте су нумерисане бројевима од \(1\) до \(n\) одозго надоле а колоне су нумерисане бројевима од \(1\) до \(m\) слева удесно. За свако \(i\) (\(1 \leq i \leq n\)) и \(j\) (\(1 \leq j \leq m\)) вредност на позицији (\(i,j\)) у матрици \(A\) (тј. на пољу у пресеку \(i\)-те врсте \(j\)-те колоне) је дефинисанa на следећи начин :

\(A_{i,j} = i \ \text{xor} \ j\)

где операција \(X \ \text{xor} \ Y\) представља ексклузивну дисјункцију бројева \(X\) и \(Y\).

Потребно је одговорити на \(q\) упита облика: Наћи вредност \(\text{xor}\)-a свих бројева у подматрици матрице \(А\) са горњим левим теменом \((x_l,y_l)\) и доњим десним теменом \((x_r,y_r)\). Подматрица матрице \(А\) са наведеним ограничењима обухвата све елементе \(A_{i,j}\) такве да важи \(x_l \leq i \leq x_r\) , \(y_l \leq j \leq y_r\).

Опис улаза

У првој линији стандардног улаза налазе се бројеви \(n, m, q\), број врста матрице \(A\), број колона матрице \(A\) и број упита на које је потребно одговорити. Наредних \(q\) линија садрже по четири броја, који предстаљају редом врсту горњег левог темена подматрице, колону горњег левог темена подматрице, врсту доњег десног темена подматрице и колону доњег десног темена подматрице.

Опис излаза

На стандардном излазу у \(q\) редова одговорити на упите описане у тексту задатка, тачније у \(i\)-а линији стандардног излаза исписати решење \(i\)-тог упита.

Пример

Улаз

4 5 3
1 1 3 3
2 3 4 5
2 3 2 4

Излаз

0
7
7

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

Матрица А је димензије \(4 \cdot 5\) и има облик:

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

Први упит задржи подматрицу са горњим левим теменом (\(1,1\)) и доњим десним (\(3,3\)). Решење овог упита је \(\text{ xor }\) свих бројева у подматрици, односно : \(0 \text{ xor } 3 \text{ xor } 2 \text{ xor } 3 \text{ xor } 0 \text{ xor } 1 \text{ xor } 2 \text{ xor } 1 \text{ xor } 0 = 0\)

Трећи упит садржи само два броја \(1\) i \(6\), тако да је решења за овај пример \(1 \text{ xor } 6 =7\)

Ограничења

\(1 \leq n,m \leq 10^9\)

\(1 \leq q \leq 10^5\)

Подзадаци

Тест примери су подељени у чeтири дисјунктне групе.

У примерима вредним 20 поена важиће ограничење \(1\leq n,m,q \leq 100\).

У примерима вредним 20 поена важиће ограничење \(1\leq n,m \leq 1000\).

У примерима вредним 30 поена важиће ограничење \(1\leq n,m \leq 10^6\).

У примерима вредним 30 поена нема додатних ограничења.

Напомена

Оператор ексклузивне дисјункције у Pascal-u је означен са xor, док у C++ га записујемо помоћу симбола ^. Ова операција \(x \ \text{xor} \ y\) се за ненегативне целе бројеве \(x,y\) дефинише на следећи начин: прво се бројеви запишу у бинарном запису. Уколико један број има мање цифара од другог, дописују му се водеће нуле све док не буду имали исти број бинарних цифара. Тако се добијају два низа бинарних цифара, означимо их са \(a_1, \ldots, a_k\) и \(b_1, \ldots b_k\). Затим се за сваку позицију \(i \in \{1, \ldots, k \}\) рачуна \(c_i\) помоћу следећих правила:

• За $a_i = 0, b_i = 0 $ важи $ c_i = 0$
• За $a_i = 0, b_i = 1 $ важи $ c_i = 1$
• За $a_i = 1, b_i = 0 $ важи $ c_i = 1$
• За $a_i = 1, b_i = 1 $ важи $ c_i = 0$

Низ бинарних цифара \(c_1, \ldots, c_k\) (који можда има водеће нуле) је бинарни запис резултата, односно броја \(x \ \text{xor} \ y\).