Дата су вам два стабла са по \(N\) чворова. Потребно је одговорити на \(Q\) упита. Сваки упит је описан са по 4 броја \(A\), \(B\), \(C\) и \(D\). Одговор на упит је број индекса \(i\) тако да се чвор са индексом \(i\) налази на путу од \(A\) до \(B\) у првом стаблу и чвор са индексом \(i\) се налази на путу од \(C\) до \(D\) у другом стаблу. Другим речима, ако је \(S1\) скуп индекса свих чворова на путу од \(A\) до \(B\) у првом стаблу и \(S2\) скуп индекса свих чворова на путу од \(C\) до \(D\) у другом стаблу, одговор на упит је \(|S1 \cap S2|\).

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

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

• \(\text{Resi}(N, Q, P, U1[\dots], V1[\dots], U2[\dots], V2[\dots], A1[\dots], B1[\dots], C1[\dots], D1[\dots], R[\dots])\)

где је: * \(N\) број чворова у стаблима * \(Q\) број упита * \(P\) параметар који се користи при израчунавању вредности низова \(A\), \(B\), \(C\) и \(D\). * \(U1\) и \(V1\) низови дужине \(N-1\) који описују гране првог стабла. \(i\)-та грана спаја чворове \(U1_i\) и \(V1_i\). * \(U2\) и \(V2\) низови дужине \(N-1\) који описују гране другог стабла. \(i\)-та грана спаја чворове \(U2_i\) и \(V2_i\). * \(A1\), \(B1\), \(C1\) и \(D1\) низови дужине \(Q\) помоћу којих се израчунавају низови \(A\), \(B\), \(C\) и \(D\) на следећи начин: Нека је \(ans_i\) одговор на \(i\)-ти упит и \(ans_0=0\). Онда је: - \(A_i = (A1_i + ans_{i-1}*P - 1) \% N + 1\) - \(B_i = (B1_i + ans_{i-1}*P - 1) \% N + 1\) - \(C_i = (C1_i + ans_{i-1}*P - 1) \% N + 1\) - \(D_i = (D1_i + ans_{i-1}*P - 1) \% N + 1\) * \(R\) низ у који треба уписати одговоре на упите.

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

Ограничења

• \(1 \leq N \leq 2 \times 10^5\)
• \(1 \leq Q \leq 2 \times 10^5\)
• \(1 \leq A[i], B[i], C[i], D[i] \leq N\)

Подзадаци

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

• [3 поена]: \(P=0\), \(N, Q \leq 1000\).
• [7 поена]: \(P=0\), \(N, Q \leq 3 \times 10^4\), оба стабла су ланци.
• [8 поена]: \(P=0\), \(N, Q \leq 3 \times 10^4\), друго стабло је ланац.
• [11 поена]: \(P=0\), \(N, Q \leq 3 \times 10^4\).
• [14 поена]: \(P=0\), оба стабла су ланци.
• [15 поена]: \(P=0\), друго стабло је ланац.
• [30 поена]: \(P=0\).
• [6 поена]: \(P=1\), оба стабла су ланци.
• [6 поена]: \(P=1\).

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

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

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

void Resi(int N, int Q, int P, int *U1, int *V1, int *U2, int *V2, int *A1, int *B1, int *C1, int *D1, int *R);

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

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

• У првом реду три броја \(N\), \(Q\) и \(P\).
• У наредних \(N-1\) редова налази се по два броја. У \(i\)-том реду \(U1_i\) и \(V1_i\).
• У наредних \(N-1\) редова налази се по два броја. У \(i\)-том реду \(U2_i\) и \(V2_i\).
• У наредних \(Q\) редова налази се по 4 броја. У \(i\)-том реду \(A1_i\), \(B1_i\), \(C1_i\) и \(D1_i\).

Затим овај програм позива вашу функцију и штампа одговоре на упите које је функција попунила у низу \(R\), по један у сваком реду.

Пример

Улаз

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

Излаз

2

Објашњење

• На путу од чвора \(5\) до чвора \(3\) у првом стаблу налазе се чворови са индексима \(1\), \(2\), \(3\) и \(5\).
• На путу од чвора \(2\) до чвора \(4\) у другом стаблу налазе се чворови са индексима \(2\), \(3\) и \(4\).
• Индекси \(2\) и \(3\) се појављују на оба пута, па је решење 2.