Дат вам је низ \(A\) од \(N\) тачака у координатној равни. Дата је и тачка \(P\). Потребно је да одговорите на \(Q\) упита. Сваки упит је описан са по два броја \(L\) и \(R\). Нека је \(S\) скуп тачака \(\{A_L, A_{L+1}, \dots A_R\}\). Дозвољено је примењивати следећу операцију произвољан број пута: узети две тачке \(H\) и \(K\) из скупа \(S\) и у скуп додати једну од тачака које се налазе на дужи \(HK\). Одговор на упит је Da ако тачка \(P\) може да се нађе у скупу \(S\) након нула или више потеза, или Ne у супротном.

Обратите пажњу на то да се координате тачака у низу \(A\) могу поклапати као и да се координате тачке \(P\) могу поклапати са координатама тачкака из низа \(A\).

Описи функција

Потребно је да имплементирате функцију

• \(\text{Resi}(N, Px, Py, X[\dots], Y[\dots], Q, L[\dots], R[\dots], O[\dots])\)

где је:

• \(N\) број тачака у низу.
• \(Px\) и \(Py\) координате тачке \(P\).
• \(X\) и \(Y\) низови који описују тачке из низа \(A\): \(i\)-та тачка има координате \(X_i\) и \(Y_i\).
• \(Q\) број упита.
• \(L\) и \(R\) низови који описују упите.
• \(O\) низ boolean вредности у који за сваки упит треба уписати true ако је одговор Da, и false ако је одговор Ne.

Сви низови су индексирани од 1.

Ограничења

• \(1 \leq N, Q \leq 3 \times 10^5\)
• \(1 \leq L_i \leq R_i \leq N\)
• Све координате су цели бројеви из интервала \([-10^9, 10^9]\)

Подзадаци

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

• [9 поена]: \(N, Q \leq 100\).
• [14 поена]: \(N, Q \leq 2500\).
• [12 поена]: \(N, Q \leq 10^5\), све тачке су на X оси, односно, \(Y_i = 0\), \(Py = 0\).
• [16 поена]: \(N, Q \leq 10^5\), постоје две праве тако да се свака тачкa из низа \(A\) налази на бар једној од њих.
• [17 поена]: \(N, Q \leq 6 \times 10^4\), све координате су цели бројеви из интервала \([-500, 500]\).
• [11 поена]: \(N, Q \leq 6 \times 10^4\).
• [21 поена]: Без додатних ограничења.

Детаљи имплементације

Потребно је да пошаљете тачно један фајл tacke.cpp који имплементира поменуту функцију. Осим тражене функције, ваш фајл може садржати и додатне глобалне променљиве, помоћне функције и додатне библиотеке.

Ваша функција мора бити следећег облика:

void Resi(int N, int Px, int Py, int *X, int *Y, int Q, int *L, int *R, bool *O);

Вашим програмима је дозвољено да мењају садржај низова, али не смеју да приступају ван њихових граница.

Уз задатак обезбеђен вам је “template” фајл code.cpp који можете користити и мењати по потреби. Такође вам је обезбеђен програм grader.cpp који служи да лакше тестирате кодове. Овај програм учитава са стандардног улаза следеће податке:

• У првом реду бројеве \(N\), \(Px\) и \(Py\).
• У наредних \(N\) редова по два броја. У \(i\)-том реду налазе се бројеви \(X_i\) и \(Y_i\).
• У наредном реду налази се број \(Q\).
• У наредних \(Q\) редова налази се по два броја: \(L_i\) и \(R_i\).

Затим овај програм позива вашу функцију и штампа одговоре на упите на стандардни излаз, по један у сваком реду. Ако је ваша функција уписала true као вредност \(O_i\), у \(i\)-том реду ће се одштампати Da, а у супротном, у \(i\)-том реду ће се одштампати Ne.

Пример

Улаз

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

Излаз

Da
Ne
Da
Da

Објашњење

• 1. упит: Почињемо од скупа \(S=\{(0, 0), (0, 3), (3, 3)\}\). Можемо да додамо тачку \((1.5, 1.5)\) која се налази на дужи \(HK\) за \(H=(0, 0)\) и \(K=(3, 3)\). Након тога можемо да додамо тачку \(P(1, 2)\) која се налази на дужи \(HK\) за \(H=(1.5, 1.5)\) и \(K=(0, 3)\), па је одговор Da.
• 2. упит: Почињемо од скупа \(S=\{(3, 3), (3, 0), (0, 0)\}\). Никако није могуће додати тачку \(P\), па је одговор Ne.
• 3. упит: Почињемо од скупа \(S=\{(0, 3), (3, 3), (3, 0)\}\). Тачка \(P(1, 2)\) се налази на дужи \(HK\) за \(H=(0, 3)\) и \(K=(3, 0)\), па је одговор Da.
• 4. упит: Можемо додати тачку \(P\) на исти начин као код првог упита, па је одговор Da.