На недавно одржаном такмичењу из програмирања, ваш тим је освојио камеру - и то не било какву камеру! Произвођач камере, фирма “MST” тврди да ова камера има невероватну способност - када се њом слика неки скуп неусмерених грана неког графа, она је у стању да израчуна да ли је могуће од тих грана формирати стабло (стабло је повезан граф без циклуса) које обухвата све чворове тог графа, и не само то! Ако се свакој од грана додели нека ненегативна целобројна тежина, она ће пронаћи оно стабло код којег је збир тежина свих грана које учествују у стаблу минималан.

Ваш задатак је да проверите да ли камера ради коректно. Вама ће бити дат правоугаони лист папира подељен на \(R\) врста и \(C\) колона, као и број \(N\) - број чворова графа. У сваком пољу налази се једна неусмерена грана, тачније, бројеви \(U_{i, j}, V_{i, j}, W_{i, j}\) (\(U_{i, j} \neq V_{i, j}\)) који значе да се у пољу \(i, j\) (\(1 \leq i \leq R, 1 \leq j \leq C\)) налази неусмерена грана која спаја чворове \(U_{i, j}, V_{i, j}\) и има тежину \(W_{i, j}\). Затим, дато вам је \(Q\) упита облика \(X_1, Y_1, X_2, Y_2\) (\(1 \leq X_1 \leq X_2 \leq R, 1 \leq Y_1 \leq Y_2 \leq C\)). Ваш задатак је да за сваки упит одредите да ли постоји стабло које повезује све чворове од \(1\) до \(N\) а чије се гране налазе у тој подматрици, тачније, узимају се у обзир само оне гране које се налазе у пољима \(x, y\) за која важи \(X_1 \leq x \leq X_2, Y_1 \leq y \leq Y_2\), а ако постоји, да одредите минималну укупну тежину таквог стабла. Како се ради о камери, важиће следеће: Означимо са \(a\) вредност \(\frac{X_2-X_1+1}{Y_2-Y_1+1}\). У свим упитима важи \(\frac{2}{3} \leq a \leq \frac{3}{2}\).

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

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

• \(Resi(N, R, C, Q, U[\ldots][\ldots], V[\ldots][\ldots], W[\ldots][\ldots], X1[\ldots], Y1[\ldots], X2[\ldots], Y2[\ldots], O[\ldots])\)

која треба да обради све упите и смести одговоре у низ \(O\). Ако стабло не постоји, у одговарајући елемент низа \(O\) уписати \(-1\), у супротном, уписати минималну тежину стабла. Сви низови су индексирани од 1.

Пример

Нека је \(N = 4, R = 3, C = 4, Q = 3\). Ради прегледности, нека је заједничка матрица тројки \((U_{i, j}, V_{i, j}, W_{i, j})\) следећа: ~~~ (1,2,1) (1,2,2) (1,2,3) (1,2,100) (2,3,2) (2,3,3) (2,3,1) (2,3,101) (3,4,3) (3,4,1) (3,4,2) (3,4,102) ~~~

а заједнички низ упита \((X_1, Y_1, X_2, Y_2)\) следећи: \((1,1,3,4), (1,2,3,3), (3,4,3,4)\). У првом упиту учествују све гране: ~~~ (1,2,1) (1,2,2) (1,2,3) (1,2,100) (2,3,2) (2,3,3) (2,3,1) (2,3,101) (3,4,3) (3,4,1) (3,4,2) (3,4,102) ~~~

Минимално стабло добијамо ако одаберемо гране \((1,2,1), (2,3,1), (3,4,1)\), па је одговор на први упит \(3\).

У другом упиту учествују следеће гране: ~~~ (1,2,1) (1,2,2) (1,2,3) (1,2,100) (2,3,2) (2,3,3) (2,3,1) (2,3,101) (3,4,3) (3,4,1) (3,4,2) (3,4,102) ~~~

Минимално стабло добијамо ако одаберемо гране \((1,2,2), (2,3,1), (3,4,1)\), па је одговор на овај упит \(4\).

У трећем упиту учествују следеће гране: ~~~ (1,2,1) (1,2,2) (1,2,3) (1,2,100) (2,3,2) (2,3,3) (2,3,1) (2,3,101) (3,4,3) (3,4,1) (3,4,2) (3,4,102) ~~~

Јасно је да стабло које повезује све чворове не постоји, па у низ \(O\) на позицији \(3\) треба уписати \(-1\).

Ограничења

• \(2 \leq N \leq 40\)
• \(1 \leq R, C \leq 250\)
• \(1 \leq Q \leq 200000\)
• \(0 \leq W_{i, j} \leq 65535\)

Подзадаци

• Подзадатак 1 [8 поена]: \(N \leq 4, R,C,Q \leq 10\)
• Подзадатак 2 [13 поена]: \(R,C,Q \leq 100\)
• Подзадатак 3 [12 поена]: \(N=2\)
• Подзадатак 4 [16 поена]: \(N=3\)
• Подзадатак 5 [20 поена]: \(Q \leq 50000\)
• Подзадатак 6 [31 поена]: без додатних ограничења

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

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

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

void Resi(int N, int R, int C, int Q, int** U, int** V, int** W, int* X1, int* Y1, int* X2, int* Y2, int* O);

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

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

• У првом реду бројеве \(N, R, C, Q\),
• У наредних \(R\) редова по \(3C\) бројева. У \(i\)-том реду налазе се бројеви \(U_{i,1}, V_{i,1}, W_{i,1}\), \(U_{i,2}, V_{i,2}, W_{i,2}\), \(\ldots\), \(U_{i,C}, V_{i,C}, W_{i,C}\),
• У наредних \(Q\) редова по 4 броја: \(X_1, Y_1, X_2, Y_2\).

Затим овај програм зове вашу функцију и штампа бројеве \(O[1], \ldots, O[Q]\), сваки у посебном реду. Кодове ових програма можете мењати по потреби.