Creació d'un BST intersecció de dos BSTs X14733

Statement

html

Donada la classe dicc que permet gestionar diccionaris on només hi guardem claus úniques usant arbres binaris de cerca (BST), cal implementar el mètode

void interseccio(const dicc<Clau> &d2, dicc<Clau> &dr) const; // Pre: El diccionari dr està buit // Post: dr conté les claus de la intersecció del p.i. amb d2

Les claus són del tipus Clau que admet una relació d’ordre total, és a dir, tenim una operació de comparació < entre claus.

Cal enviar a jutge.org la següent especificació de la classe dicc i la implementació del mètode dins del mateix fitxer. La resta de mètodes públics i privats ja estan implementats. Indica dins d’un comentari a la capçalera del mètode el seu cost en funció del nombre d’elements n1 del diccionari del p.i. i nombre d’elements n2 del diccionari d2.

#include <iostream> using namespace std; typedef unsigned int nat; template <typename Clau> class dicc { public: // Constructora per defecte. Crea un diccionari buit. dicc(); // Destructora ~dicc(); // Insereix la clau k en el diccionari. Si ja hi era, no fa res. void insereix(const Clau &k); // Imprimeix els elements del diccionari ordenats de menor a major void print() const; // Retorna la mida del BST que implementa el diccionari nat mida() const; // Retorna l’altura del BST que implementa el diccionari nat altura() const; void interseccio(const dicc<Clau> &d2, dicc<Clau> &dr) const; // Pre: El diccionari dr està buit // Post: dr conté les claus de la intersecció del p.i. amb d2 private: struct node { Clau _k; // Clau node* _esq; // fill esquerre node* _dret; // fill dret node(const Clau &k, node* esq = NULL, node* dret = NULL); }; node *_arrel; static void esborra_nodes(node* m); static node* insereix_bst(node *n, const Clau &k); static void print(node *n); static nat mida(node *n); static nat altura(node *n); // Aquí va l’especificació dels mètodes privats addicionals }; // Aquí va la implementació dels mètodes públics i privats

Degut a que jutge.org només permet l’enviament d’un fitxer amb la solució del problema, en el mateix fitxer hi ha d’haver l’especificació de la classe i la implementació del mètode interseccio (el que normalment estarien separats en els fitxers .hpp i .cpp).

Per testejar la classe disposes d’un programa principal que llegeix dos diccionaris d’enters, desprès crida el mètode interseccio i finalment mostra el contingut del diccionari amb la intersecció dels dos diccionaris inicials. També s’indica si el BST del diccionari resultant està suficientment balancejat.

Entrada

L’entrada conté dues línies formades per seqüències d’enters, són els elements que tindran els dos diccionaris inicials.

Sortida

A la sortida apareixen ordenats i separats per espais, els elements del diccionari resultant que conté la intersecció dels dos diccionaris inicials. A la segona línia apareix el text "BST poc balancejat" o "BST suficient balancejat", depenen de si l’altura del BST resultant supera o no min (mida, log₂(mida) * 10), sent mida el nombre de nodes de l’arbre resultant.

Observació

Només cal enviar l’especificació de la classe dicc, la implementació del mètode interseccio i el seu cost en funció del nombre d’elements n1 i n2 dels dos diccionaris inicials. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Primer cal crear un BST amb el resultat correcte. Posteriorment obtenir un BST més balancejat si no ho està suficientment. Hi ha diferents tècniques per aconseguir-ho, una d’elles és alternar de forma aleatòria l’ordre en que es recorren els BSTs inicials (esquerra-dreta o dreta-esquerra), et pot ser d’utilitat l’expressió rand() % 2 que simula el cara/creu d’una moneda llançada a l’aire, el seu resultat és 0 o 1.

Els primers tres exemples mostren la intersecció de dos diccionaris buits o un de buit i un que no ho és.

Public test cases

Input

Output

BST suficient balancejat

Input

5 -3 8 2 -1 7 -7 -6

Output

BST suficient balancejat

Input

 
7 -2 9 5 -3 2 -7

Output

BST suficient balancejat

Input

5 -3 8 2 -1 7 -7 -6
7 -2 9 5 -3 2 -7

Output

-7 -3 2 5 7 
BST suficient balancejat

Input

5 -5 -3 9 -9 2 -2 1 -1 7 -7 0 4 -4 8 -8 6
2 10 4 12 8 14 0 10 14 6

Output

0 2 4 6 8 
BST suficient balancejat

Input

-191 427 -13 -2 -11 353 10 -333 -85 -4763 400 1 -29 4 -3 3 33 39 573 -447 453 -4743 15 -2713 151 240 -4 29 -159 -1 481 113 -31 250 2 262 273 4853 443 483 143 99 -81 -4313 49 -430 1033 -23 -33 -30 -494 48 -1663 -345 403 -59 -32 457 43 -44 -473 433 -399 -19 4753 -9 30 103 474 16 233 20 -233 473 -25 -405 -203 -215 -41 -119 -442 -15 40 489 -4543 27 223 53 14 -43 -213 -171 -40 133 9 36 -492 -73 -47 -64 423 -1223 382 703 201 -130 25 23 -27 -163 3193 492 18 1123 44 -189 -10 -312 -353 -313 206 179 199 169 -6 -37 4549 35 5 1813 -470 19 -423 -414 -39 93 -21 263 373 45 -266 -2819 -2433 -51 -20 2873 294 -14 -4653 1763 -793 -443 12 -490 -461 -410 719 -362 22 -103 -3353 -223 593 -325 -302 191 -431 -17 120 -24 163 -3069 47 173 -322 -101 -3433 46 13 392 -475 172 -99 -380 -87 -433 -439 38 4933 -122 211 459 -319 31 255 -280 -26 295 -4803 42 -310 -36 -479 -271 -411 -362 333 -166 -283 -3243 -35 237 162 369 -469 -4463 11 -360 4543 -60 100 380 -424 869 -179 -5 -493 -323 3213 -45 21 2633 -46 3523 -420 102 -320 -92 83 -219 -499 -4363 -183 231 -236 -150 -86 383 -355 94 -403 89 161 -245 278 4833 -2543 37 -22 6 -42 230 -131 -391 204 41 -263 3943 80 -169 -393 183 -3253 51 461 -149 -89 3233 24 -109 -1013 34 449 499 4349 17 -3943 -300 -210 26 281 -342 -229 -432 1023 2113 -260 -49 440 1963 -369 -273 129 -28 309 302 376 -913 -220 -274 -226 -4893 203 360 -270 -195 342 391 -82 -141 -4063 -382 -1129 -400 -346 -390 -489 215 282 -16 2133 -440 -2193 351 252 421 -261 401 -38 243 -112 4913 170 999 189 413 -100 -573 -3643 -463 -407 -12 2033 208 -291 -422 -409 -279 -193 -133 519 -330 -239 387 1009 -143 270 4273 393 303 472 225 -435 -450 109 2933 3733 -184 -4633 -48 490 2003 2353 283 430 -4263 241 4163 -4533 236 -365 4253 4063 -4553 -361 -173 -153 4573 -481 1683 493 7 284 381 3293 253 356 432 62 -241 434 123 -84 1313 119 180 389 150 -2493 261 359 140 195 -1543 -383 -72 -395 1363 -2233 -129 299 4843 -4033 -299 4149 -379 -61 450 2563 2413 -372 402 352 -91 683 480 469 -491 -2463 1303 -340 363 -170 -436 -160 -2483 91 -482 -370 305 -243 -4643 121 2849 455 293 3263 3243 1993 4813 -135 372 -93 2333 181 -373 -321 -50 -4919 -343 -3723 313 -1983 110 -1043 -34 -324 -8 3763 -253 4243 131 -3393 -69 1203 -3613 4233 200 79 -2723 395 463 350 -893 -1923 -192 -354 3713 -1693 343 4653 -311 193 -113 -480 -4253 32 -413 254 -196 4873 -392 -341 -351 4249 2453 -3453 2343 73 3853 235 -453 160 220 171 -161 -107 -3773 -217 -74 -1743 -2813 330 -180 -182 -80 -4433 -339 139 -120 291 -3113 -65 280 361 -363 149 -110 -1813 3623 154 -653 -132 -474 167 3053 -415 -123 269 -294 275 184 260 1233 370 -1483 379 339 153 -3473 -1143 913 4453 2299 55 -1423 2013 -293 -371 341 3113 -2113 229 441 -63 -485 92 311 4723 3779 4379 -4623 239 -142 -429 1483 323 -401 -2373 4663 1173 314 135 4503 320 409 -334 -1203 -105 -452 -4833 -199 -421 460 -2163 -543 304 8 479 -1063 -394 355 -221 -2309 -83 -533 -329 3673 2913 219 145 141 -259 -164 -79 -2049 210 -384 -3553 272 -240 1713 190 963 -349 112 -145 -234 257 159 334 -244 -1173 4649 -2523 -2329 301 70 289 3023 -151 -350 142 -465 -2923 2833 -444 -1553 -1623 1513 -3003 72 -381 4553 292 -364 244 -483 415 -419 -3693 -124 -1823 1839 -18 279 63 -3993 2573 192 1703 74 111 3793 -267 -52 -2053 -4123 -4153 130 -4683 3833 399 -4963 -4889 -115 410 329 -1633 259 -139 471 -663 -53 -455 114 3753 76 -3843 249 414 1403 -7 -275 -1263 743 50 -232 3983 -3733 4293 1263 1293 3219 -309 -389 -214 3603 2283 209 344 1543 -3063 -484 -71 274 -2323 673 358 -451 -290 3973 122 -3923 -3273 152 1953 -2973 -4913 -1053 -225 439 -783 -1299 405 3133 -3663 2463 297 -3193 65 -425 2693 2899 452 256 319 226 -3153 -272 -336 -54 470 484 -2383 3883 52 -303 116 -235 371 -4149 -487 -359 4373 -292 4133 -2263 -1333 -96 419 349 -993 1793 -76 -257 221 -3173 -264 3043 643 429 -2733 -211 271 933 -231 -3919 420 -4439 -1863 -256 -3103 -4203 -3803 1573 -366 -464 -4353 -344 494 -70 -106 -2799 1653 -190 -4293 115 82 1433 28 -1683 157 -3413 -643 -434 54 -201 174 59 -3579 125 60 -2903 213 -513 155 326 -2123 -269 354 165 -496 101 234 -254 175 -216 -3143 -304 1523 1883 3279 -306 2673 2753 -285 2263 -563 -137 242 -282 1299 97 442 -347 331 -3483 4773 324 337 -460 -154 4563 4383 -209 105 366 -2943 310 -327 69 -3933 462 4943 -62 -2893 424 -3653 2669 -242 993 -358 -230 437 -140 -181 843 -249 -289 -2029 232 -284 435 -2313 533 3723 -1283 -1113 -2393 -268 398 390 -3329 1603 2269 -1653 -2623 4683 464 1153 4963 1873 315 -863 3453 -3513 251 -1073 186 -1393 3103 290 -252 -4059 406 -251 132 -929 -2513 2683 -2503 136 1753 -386 3903 147 176 265 -441 3503 3703 -1993 64 -2563 -873 2623 -472 456 523 124 -509 2223 -454 -1749 364 411 -352 -2043 1333 2769 -404 -2833 164 1989 543 4623 224 61 431 336 4363 212 -3563 -2303 222 -943 4223 386 -883 -200 -3713 -111 84 -265 -3249 196 3483 2393 -2443 3873 90 -1523 -2343 -4053 -457 -4883 -1453 -1353 -2213 -4233 -308 3303 1773 475 3353 -2913 1863 -1463 -2679 348 -4223 446 -172 -459 4203 2313 -3983 -2553 -3303 444 422 -155 247 -833 -1909 194 -2653 137 4803 -2423 753 -1433 -1713 1553 4709 3563 -374 -3753 -246 -295 -4719 3203 -375 144 287 374 451 3273 -3669 3743 182 312 4809 -763 2273 485 4143 -4283 447 -3123 264 375 -146 -449 -2789 66 -4333 3993 -2919 -1293 -2023 404 -3279 -412 4313 -2643 71 923 345 3633 1163 -1253 -4593 214 -4753 4793 -174 -281 1493 -1153 -2593 -1493 -713 -983 -3089 1833 3533 3143 -3183 1733 340 973 4769 3323 491 -1873 4643 -167 3843 3083 -94 300 -3083 -2273 4763 -1929 202 -162 156 185 -104 -437 67 -288 4173 -90 -446 -693 4053 -2983 -4783 -305 1723 723 -488 2303 454 3063 2993 -2763 4893 -1123 496 -3813 2143 -2103 -152 -2873 4693 -456 482 2853 -3973 -2783 -116 4953 2733 -1953 -2269 205 1983 3863 -4853 3463 1343 276 -2403 529 -144 -2413 2923 -4323 3923 -4749 3253 563 57 3573 -136 -3893 -699 134 -1323 -3873 -495 3343 -1963 3409 -4903 -1273 -3673 -589 -623 -121 983 669 228 -3073 -222 335 3173 1073 -427 -2319 -4993 -224 321 81 3583 332 4733 -1789 -2083 -486 2099 -471 1113 3773 -879 88 4113 -77 -3399 -3609 -2153 -186 3419 -2093 -462 1943 2743 -3963 412 -1819 4213 -197 322 2903 1719 -2189 2613 -4003 -1216
-4763 400 -4743 -2713 4853 443 483 4313 430 1033 -1663 -345 403 4753 -4543 -1223 382 703 201 -130 25 23 -27 -163 3193 492 18 1123 44 -189 -10 -312 -353 -313 206 179 199 169 -6 -37 4549 35 5 1813 -470 19 -423 -414 -39 93 -21 263 373 45 -266 -2819 -2433 -51 -20 2873 294 -14 -4653 1763 -793 -443 12 -490 -461 -410 719 -362 22 -103 -3353 -223 593 -325 -302 191 -431 -17 120 -24 163 -3069 47 173 -322 -101 -3433 46 13 392 -475 172 -99 -380 -87 -433 -439 38 4933 -122 211 459 -319 31 255 -280 -26 295 -4803 42 -310 -36 -479 -271 -411 -362 333 -166 -283 -3243 -35 237 162 369 -469 -4463 11 -360 4543 -60 100 380 -424 869 -179 -5 -493 -323 3213 -45 21 2633 -46 3523 -420 102 -320 -92 83 -219 -499 -4363 -183 231 -236 -150 -86 383 -355 94 -403 89 161 -245 278 4833 -2543 37 -22 6 -42 230 -131 -391 204 41 -263 3943 80 -169 -393 183 -3253 51 461 -149 -89 3233 24 -109 -1013 34 449 499 4349 17 -3943 -300 -210 26 281 -342 -229 -432 1023 2113 -260 -49 440 1963 -369 -273 129 -28 309 302 376 -913 -220 -274 -226 -4893 203 360 -270 -195 342 391 -82 -141 -4063 -382 -1129 -400 -346 -390 -489 215 282 -16 2133 -440 -2193 351 252 421 -261 401 -38 243 -112 4913 170 999 189 413 -100 -573 -3643 -463 -407 -12 2033 208 -291 -422 -409 -279 -193 -133 519 -330 -239 387 1009 -143 270 4273 393 303 472 225 -435 -450 109 2933 3733 -184 -4633 -48 490 2003 2353 283 430 -4263 241 4163 -4533 236 -365 4253 4063 -4553 -361 -173 -153 4573 -481 1683 493 7 284 381 3293 253 356 432 62 -241 434 123 -84 1313 119 180 389 150 -2493 261 359 140 195 -1543 -383 -72 -395 1363 -2233 -129 299 4843 -4033 -299 4149 -379 -61 450 2563 2413 -372 402 352 -91 683 480 469 -491 -2463 1303 -340 363 -170 -436 -160 -2483 91 -482 -370 305 -243 -4643 121 2849 455 293 3263 3243 1993 4813 -135 372 -93 2333 181 -373 -321 -50 -4919 -343 -3723 313 -1983 110 -1043 -34 -324 -8 3763 -253 4243 131 -3393 -69 1203 -3613 4233 200 79 -2723 395 463 350 -893 -1923 -192 -354 3713 -1693 343 4653 -311 193 -113 -480 -4253 32 -413 254 -196 4873 -392 -341 -351 4249 2453 -3453 2343 73 3853 235 -453 160 220 171 -161 -107 -3773 -217 -74 -1743 -2813 330 -180 -182 -80 -4433 -339 139 -120 291 -3113 -65 280 361 -363 149 -110 -1813 3623 154 -653 -132 -474 167 3053 -415 -123 269 -294 275 184 260 1233 370 -1483 379 339 153 -3473 -1143 913 4453 2299 55 -1423 2013 -293 -371 341 3113 -2113 229 441 -63 -485 92 311 4723 3779 4379 -4623 239 -142 -429 1483 323 -401 -2373 4663 1173 314 135 4503 320 409 -334 -1203 -105 -452 -4833 -199 -421 460 -2163 -543 304 8 479 -1063 -394 355 -221 -2309 -83 -533 -329 3673 2913 219 145 141 -259 -164 -79 -2049 210 -384 -3553 272 -240 1713 190 963 -349 112 -145 -234 257 159 334 -244 -1173 4649 -2523 -2329 301 70 289 3023 -151 -350 142 -465 -2923 2833 -444 -1553 -1623 1513 -3003 72 -381 4553 292 -364 244 -483 415 -419 -3693 -124 -1823 1839 -18 279 63 -3993 2573 192 1703 74 111 3793 -267 -52 -2053 -4123 -4153 130 -4683 3833 399 -4963 -4889 -115 410 329 -1633 259 -139 471 -663 -53 -455 114 3753 76 -3843 249 414 1403 -7 -275 -1263 743 50 -232 3983 -3733 4293 1263 1293 3219 -309 -389 -214 3603 2283 209 344 1543 -3063 -484 -71 274 -2323 673 358 -451 -290 3973 122 -3923 -3273 152 1953 -2973 -4913 -1053 -225 439 -783 -1299 405 3133 -3663 2463 297 -3193 65 -425 2693 2899 452 256 319 226 -3153 -272 -336 -54 470 484 -2383 3883 52 -303 116 -235 371 -4149 -487 -359 4373 -292 4133 -2263 -1333 -96 419 349 -993 1793 -76 -257 221 -3173 -264 3043 643 429 -2733 -211 271 933 -231 -3919 420 -4439 -1863 -256 -3103 -4203 -3803 1573 -366 -464 -4353 -344 494 -70 -106 -2799 1653 -190 -4293 115 82 1433 28 -1683 157 -3413 -643 -434 54 -201 174 59 -3579 125 60 -2903 213 -513 155 326 -2123 -269 354 165 -496 101 234 -254 175 -216 -3143 -304 1523 1883 3279 -306 2673 2753 -285 2263 -563 -137 242 -282 1299 97 442 -347 331 -3483 4773 324 337 -460 -154 4563 4383 -209 105 366 -2943 310 -327 69 -3933 462 4943 -62 -2893 424 -3653 2669 -242 993 -358 -230 437 -140 -181 843 -249 -289 -2029 232 -284 435 -2313 533 3723 -1283 -1113 -2393 -268 398 390 -3329 1603 2269 -1653 -2623 4683 464 1153 4963 1873 315 -863 3453 -3513 251 -1073 186 -1393 3103 290 -252 -4059 406 -251 132 -929 -2513 2683 -2503 136 1753 -386 3903 147 176 265 -441 3503 3703 -1993 64 -2563 -873 2623 -472 456 523 124 -509 2223 -454 -1749 364 411 -352 -2043 1333 2769 -404 -2833 164 1989 543 4623 224 61 431 336 4363 212 -3563 -2303 222 -943 4223 386 -883 -200 -3713 -111 84 -265 -3249 196 3483 2393 -2443 3873 90 -1523 -2343 -4053 -457 -4883 -1453 -1353 -2213 -4233 -308 3303 1773 475 3353 -2913 1863 -1463 -2679 348 -4223 446 -172 -459 4203 2313 -3983 -2553 -3303 444 422 -155 247 -833 -1909 194 -2653 137 4803 -2423 753 -1433 -1713 1553 4709 3563 -374 -3753 -246 -295 -4719 3203 -375 144 287 374 451 3273 -3669 3743 182 312 4809 -763 2273 485 4143 -4283 447 -3123 264 375 -146 -449 -2789 66 -4333 3993 -2919 -1293 -2023 404 -3279 -412 4313 -2643 71 923 345 3633 1163 -1253 -4593 214 -4753 4793 -174 -281 1493 -1153 -2593 -1493 -713 -983 -3089 1833 3533 3143 -3183 1733 340 973 4769 3323 491 -1873 4643 -167 3843 3083 -94 300 -3083 -2273 4763 -1929 202 -162 156 185 -104 -437 67 -288 4173 -90 -446 -693 4053 -2983 -4783 -305 1723 723 -488 2303 454 3063 2993 -2763 4893 -1123 496 -3813 2143 -2103 -152 -2873 4693 -456 482 2853 -3973 -2783 -116 4953 2733 -1953 -2269 205 1983 3863 -4853 3463 1343 276 -2403 529 -144 -2413 2923 -4323 3923 -4749 3253 563 57 3573 -136 -3893 -699 134 -1323 -3873 -495 3343 -1963 3409 -4903 -1273 -3673 -589 -623 -121 983 669 228 -3073 -222 335 3173 1073 -427 -2319 -4993 -224 321 81 3583 332 4733 -1789 -2083 -486 2099 -471 1113 3773 -879 88 4113 -77 -3399 -3609 -2153 -186 3419 -2093 -462 1943 2743 -3963 412 -1819 4213 -197 322 2903 1719 -2189 2613 -4003 -1216

Output

-4993 -4963 -4919 -4913 -4903 -4893 -4889 -4883 -4853 -4833 -4803 -4783 -4763 -4753 -4749 -4743 -4719 -4683 -4653 -4643 -4633 -4623 -4593 -4553 -4543 -4533 -4463 -4439 -4433 -4363 -4353 -4333 -4323 -4293 -4283 -4263 -4253 -4233 -4223 -4203 -4153 -4149 -4123 -4063 -4059 -4053 -4033 -4003 -3993 -3983 -3973 -3963 -3943 -3933 -3923 -3919 -3893 -3873 -3843 -3813 -3803 -3773 -3753 -3733 -3723 -3713 -3693 -3673 -3669 -3663 -3653 -3643 -3613 -3609 -3579 -3563 -3553 -3513 -3483 -3473 -3453 -3433 -3413 -3399 -3393 -3353 -3329 -3303 -3279 -3273 -3253 -3249 -3243 -3193 -3183 -3173 -3153 -3143 -3123 -3113 -3103 -3089 -3083 -3073 -3069 -3063 -3003 -2983 -2973 -2943 -2923 -2919 -2913 -2903 -2893 -2873 -2833 -2819 -2813 -2799 -2789 -2783 -2763 -2733 -2723 -2713 -2679 -2653 -2643 -2623 -2593 -2563 -2553 -2543 -2523 -2513 -2503 -2493 -2483 -2463 -2443 -2433 -2423 -2413 -2403 -2393 -2383 -2373 -2343 -2329 -2323 -2319 -2313 -2309 -2303 -2273 -2269 -2263 -2233 -2213 -2193 -2189 -2163 -2153 -2123 -2113 -2103 -2093 -2083 -2053 -2049 -2043 -2029 -2023 -1993 -1983 -1963 -1953 -1929 -1923 -1909 -1873 -1863 -1823 -1819 -1813 -1789 -1749 -1743 -1713 -1693 -1683 -1663 -1653 -1633 -1623 -1553 -1543 -1523 -1493 -1483 -1463 -1453 -1433 -1423 -1393 -1353 -1333 -1323 -1299 -1293 -1283 -1273 -1263 -1253 -1223 -1216 -1203 -1173 -1153 -1143 -1129 -1123 -1113 -1073 -1063 -1053 -1043 -1013 -993 -983 -943 -929 -913 -893 -883 -879 -873 -863 -833 -793 -783 -763 -713 -699 -693 -663 -653 -643 -623 -589 -573 -563 -543 -533 -513 -509 -499 -496 -495 -493 -491 -490 -489 -488 -487 -486 -485 -484 -483 -482 -481 -480 -479 -475 -474 -472 -471 -470 -469 -465 -464 -463 -462 -461 -460 -459 -457 -456 -455 -454 -453 -452 -451 -450 -449 -446 -444 -443 -441 -440 -439 -437 -436 -435 -434 -433 -432 -431 -429 -427 -425 -424 -423 -422 -421 -420 -419 -415 -414 -413 -412 -411 -410 -409 -407 -404 -403 -401 -400 -395 -394 -393 -392 -391 -390 -389 -386 -384 -383 -382 -381 -380 -379 -375 -374 -373 -372 -371 -370 -369 -366 -365 -364 -363 -362 -361 -360 -359 -358 -355 -354 -353 -352 -351 -350 -349 -347 -346 -345 -344 -343 -342 -341 -340 -339 -336 -334 -330 -329 -327 -325 -324 -323 -322 -321 -320 -319 -313 -312 -311 -310 -309 -308 -306 -305 -304 -303 -302 -300 -299 -295 -294 -293 -292 -291 -290 -289 -288 -285 -284 -283 -282 -281 -280 -279 -275 -274 -273 -272 -271 -270 -269 -268 -267 -266 -265 -264 -263 -261 -260 -259 -257 -256 -254 -253 -252 -251 -249 -246 -245 -244 -243 -242 -241 -240 -239 -236 -235 -234 -232 -231 -230 -229 -226 -225 -224 -223 -222 -221 -220 -219 -217 -216 -214 -211 -210 -209 -201 -200 -199 -197 -196 -195 -193 -192 -190 -189 -186 -184 -183 -182 -181 -180 -179 -174 -173 -172 -170 -169 -167 -166 -164 -163 -162 -161 -160 -155 -154 -153 -152 -151 -150 -149 -146 -145 -144 -143 -142 -141 -140 -139 -137 -136 -135 -133 -132 -131 -130 -129 -124 -123 -122 -121 -120 -116 -115 -113 -112 -111 -110 -109 -107 -106 -105 -104 -103 -101 -100 -99 -96 -94 -93 -92 -91 -90 -89 -87 -86 -84 -83 -82 -80 -79 -77 -76 -74 -72 -71 -70 -69 -65 -63 -62 -61 -60 -54 -53 -52 -51 -50 -49 -48 -46 -45 -42 -39 -38 -37 -36 -35 -34 -28 -27 -26 -24 -22 -21 -20 -18 -17 -16 -14 -12 -10 -8 -7 -6 -5 5 6 7 8 11 12 13 17 18 19 21 22 23 24 25 26 28 31 32 34 35 37 38 41 42 44 45 46 47 50 51 52 54 55 57 59 60 61 62 63 64 65 66 67 69 70 71 72 73 74 76 79 80 81 82 83 84 88 89 90 91 92 93 94 97 100 101 102 105 109 110 111 112 114 115 116 119 120 121 122 123 124 125 129 130 131 132 134 135 136 137 139 140 141 142 144 145 147 149 150 152 153 154 155 156 157 159 160 161 162 163 164 165 167 169 170 171 172 173 174 175 176 179 180 181 182 183 184 185 186 189 190 191 192 193 194 195 196 199 200 201 202 203 204 205 206 208 209 210 211 212 213 214 215 219 220 221 222 224 225 226 228 229 230 231 232 234 235 236 237 239 241 242 243 244 247 249 251 252 253 254 255 256 257 259 260 261 263 264 265 269 270 271 272 274 275 276 278 279 280 281 282 283 284 287 289 290 291 292 293 294 295 297 299 300 301 302 303 304 305 309 310 311 312 313 314 315 319 320 321 322 323 324 326 329 330 331 332 333 334 335 336 337 339 340 341 342 343 344 345 348 349 350 351 352 354 355 356 358 359 360 361 363 364 366 369 370 371 372 373 374 375 376 379 380 381 382 383 386 387 389 390 391 392 393 395 398 399 400 401 402 403 404 405 406 409 410 411 412 413 414 415 419 420 421 422 424 429 430 431 432 434 435 437 439 440 441 442 443 444 446 447 449 450 451 452 454 455 456 459 460 461 462 463 464 469 470 471 472 475 479 480 482 483 484 485 490 491 492 493 494 496 499 519 523 529 533 543 563 593 643 669 673 683 703 719 723 743 753 843 869 913 923 933 963 973 983 993 999 1009 1023 1033 1073 1113 1123 1153 1163 1173 1203 1233 1263 1293 1299 1303 1313 1333 1343 1363 1403 1433 1483 1493 1513 1523 1543 1553 1573 1603 1653 1683 1703 1713 1719 1723 1733 1753 1763 1773 1793 1813 1833 1839 1863 1873 1883 1943 1953 1963 1983 1989 1993 2003 2013 2033 2099 2113 2133 2143 2223 2263 2269 2273 2283 2299 2303 2313 2333 2343 2353 2393 2413 2453 2463 2563 2573 2613 2623 2633 2669 2673 2683 2693 2733 2743 2753 2769 2833 2849 2853 2873 2899 2903 2913 2923 2933 2993 3023 3043 3053 3063 3083 3103 3113 3133 3143 3173 3193 3203 3213 3219 3233 3243 3253 3263 3273 3279 3293 3303 3323 3343 3353 3409 3419 3453 3463 3483 3503 3523 3533 3563 3573 3583 3603 3623 3633 3673 3703 3713 3723 3733 3743 3753 3763 3773 3779 3793 3833 3843 3853 3863 3873 3883 3903 3923 3943 3973 3983 3993 4053 4063 4113 4133 4143 4149 4163 4173 4203 4213 4223 4233 4243 4249 4253 4273 4293 4313 4349 4363 4373 4379 4383 4453 4503 4543 4549 4553 4563 4573 4623 4643 4649 4653 4663 4683 4693 4709 4723 4733 4753 4763 4769 4773 4793 4803 4809 4813 4833 4843 4853 4873 4893 4913 4933 4943 4953 4963 
BST suficient balancejat

Input

-191 427 -13 -2 -11 353 10 -333 -85 -4763 400 1 -29 4 -3 3 33 39 573 -447 453 -4743 15 -2713 151 240 -4 29 -159 -1 481 113 -31 250 2 262 273 4853 443 483 143 99 -81 -4313 49 -430 1033 -23 -33 -30 -494 48 -1663 -345 403 -59 -32 457 43 -44 -473 433 -399 -19 4753 -9 30 103 474 16 233 20 -233 473 -25 -405 -203 -215 -41 -119 -442 -15 40 489 -4543 27 223 53 14 -43 -213 -171 -40 133 9 36 -492 -73 -47 -64 423 -1223 382 703 201 -130 25 23 -27 -163 3193 492 18 1123 44 -189 -10 -312 -353 -313 206 179 199 169 -6 -37 4549 35 5 1813 -470 19 -423 -414 -39 93 -21 263 373 45 -266 -2819 -2433 -51 -20 2873 294 -14 -4653 1763 -793 -443 12 -490 -461 -410 719 -362 22 -103 -3353 -223 593 -325 -302 191 -431 -17 120 -24 163 -3069 47 173 -322 -101 -3433 46 13 392 -475 172 -99 -380 -87 -433 -439 38 4933 -122 211 459 -319 31 255 -280 -26 295 -4803 42 -310 -36 -479 -271 -411 -362 333 -166 -283 -3243 -35 237 162 369 -469 -4463 11 -360 4543 -60 100 380 -424 869 -179 -5 -493 -323 3213 -45 21 2633 -46 3523 -420 102 -320 -92 83 -219 -499 -4363 -183 231 -236 -150 -86 383 -355 94 -403 89 161 -245 278 4833 -2543 37 -22 6 -42 230 -131 -391 204 41 -263 3943 80 -169 -393 183 -3253 51 461 -149 -89 3233 24 -109 -1013 34 449 499 4349 17 -3943 -300 -210 26 281 -342 -229 -432 1023 2113 -260 -49 440 1963 -369 -273 129 -28 309 302 376 -913 -220 -274 -226 -4893 203 360 -270 -195 342 391 -82 -141 -4063 -382 -1129 -400 -346 -390 -489 215 282 -16 2133 -440 -2193 351 252 421 -261 401 -38 243 -112 4913 170 999 189 413 -100 -573 -3643 -463 -407 -12 2033 208 -291 -422 -409 -279 -193 -133 519 -330 -239 387 1009 -143 270 4273 393 303 472 225 -435 -450 109 2933 3733 -184 -4633 -48 490 2003 2353 283 430 -4263 241 4163 -4533 236 -365 4253 4063 -4553 -361 -173 -153 4573 -481 1683 493 7 284 381 3293 253 356 432 62 -241 434 123 -84 1313 119 180 389 150 -2493 261 359 140 195 -1543 -383 -72 -395 1363 -2233 -129 299 4843 -4033 -299 4149 -379 -61 450 2563 2413 -372 402 352 -91 683 480 469 -491 -2463 1303 -340 363 -170 -436 -160 -2483 91 -482 -370 305 -243 -4643 121 2849 455 293 3263 3243 1993 4813 -135 372 -93 2333 181 -373 -321 -50 -4919 -343 -3723 313 -1983 110 -1043 -34 -324 -8 3763 -253 4243 131 -3393 -69 1203 -3613 4233 200 79 -2723 395 463 350 -893 -1923 -192 -354 3713 -1693 343 4653 -311 193 -113 -480 -4253 32 -413 254 -196 4873 -392 -341 -351 4249 2453 -3453 2343 73 3853 235 -453 160 220 171 -161 -107 -3773 -217 -74 -1743 -2813 330 -180 -182 -80 -4433 -339 139 -120 291 -3113 -65 280 361 -363 149 -110 -1813 3623 154 -653 -132 -474 167 3053 -415 -123 269 -294 275 184 260 1233 370 -1483 379 339 153 -3473 -1143 913 4453 2299 55 -1423 2013 -293 -371 341 3113 -2113 229 441 -63 -485 92 311 4723 3779 4379 -4623 239 -142 -429 1483 323 -401 -2373 4663 1173 314 135 4503 320 409 -334 -1203 -105 -452 -4833 -199 -421 460 -2163 -543 304 8 479 -1063 -394 355 -221 -2309 -83 -533 -329 3673 2913 219 145 141 -259 -164 -79 -2049 210 -384 -3553 272 -240 1713 190 963 -349 112 -145 -234 257 159 334 -244 -1173 4649 -2523 -2329 301 70 289 3023 -151 -350 142 -465 -2923 2833 -444 -1553 -1623 1513 -3003 72 -381 4553 292 -364 244 -483 415 -419 -3693 -124 -1823 1839 -18 279 63 -3993 2573 192 1703 74 111 3793 -267 -52 -2053 -4123 -4153 130 -4683 3833 399 -4963 -4889 -115 410 329 -1633 259 -139 471 -663 -53 -455 114 3753 76 -3843 249 414 1403 -7 -275 -1263 743 50 -232 3983 -3733 4293 1263 1293 3219 -309 -389 -214 3603 2283 209 344 1543 -3063 -484 -71 274 -2323 673 358 -451 -290 3973 122 -3923 -3273 152 1953 -2973 -4913 -1053 -225 439 -783 -1299 405 3133 -3663 2463 297 -3193 65 -425 2693 2899 452 256 319 226 -3153 -272 -336 -54 470 484 -2383 3883 52 -303 116 -235 371 -4149 -487 -359 4373 -292 4133 -2263 -1333 -96 419 349 -993 1793 -76 -257 221 -3173 -264 3043 643 429 -2733 -211 271 933 -231 -3919 420 -4439 -1863 -256 -3103 -4203 -3803 1573 -366 -464 -4353 -344 494 -70 -106 -2799 1653 -190 -4293 115 82 1433 28 -1683 157 -3413 -643 -434 54 -201 174 59 -3579 125 60 -2903 213 -513 155 326 -2123 -269 354 165 -496 101 234 -254 175 -216 -3143 -304 1523 1883 3279 -306 2673 2753 -285 2263 -563 -137 242 -282 1299 97 442 -347 331 -3483 4773 324 337 -460 -154 4563 4383 -209 105 366 -2943 310 -327 69 -3933 462 4943 -62 -2893 424 -3653 2669 -242 993 -358 -230 437 -140 -181 843 -249 -289 -2029 232 -284 435 -2313 533 3723 -1283 -1113 -2393 -268 398 390 -3329 1603 2269 -1653 -2623 4683 464 1153 4963 1873 315 -863 3453 -3513 251 -1073 186 -1393 3103 290 -252 -4059 406 -251 132 -929 -2513 2683 -2503 136 1753 -386 3903 147 176 265 -441 3503 3703 -1993 64 -2563 -873 2623 -472 456 523 124 -509 2223 -454 -1749 364 411 -352 -2043 1333 2769 -404 -2833 164 1989 543 4623 224 61 431 336 4363 212 -3563 -2303 222 -943 4223 386 -883 -200 -3713 -111 84 -265 -3249 196 3483 2393 -2443 3873 90 -1523 -2343 -4053 -457 -4883 -1453 -1353 -2213 -4233 -308 3303 1773 475 3353 -2913 1863 -1463 -2679 348 -4223 446 -172 -459 4203 2313 -3983 -2553 -3303 444 422 -155 247 -833 -1909 194 -2653 137 4803 -2423 753 -1433 -1713 1553 4709 3563 -374 -3753 -246 -295 -4719 3203 -375 144 287 374 451 3273 -3669 3743 182 312 4809 -763 2273 485 4143 -4283 447 -3123 264 375 -146 -449 -2789 66 -4333 3993 -2919 -1293 -2023 404 -3279 -412 4313 -2643 71 923 345 3633 1163 -1253 -4593 214 -4753 4793 -174 -281 1493 -1153 -2593 -1493 -713 -983 -3089 1833 3533 3143 -3183 1733 340 973 4769 3323 491 -1873 4643 -167 3843 3083 -94 300 -3083 -2273 4763 -1929 202 -162 156 185 -104 -437 67 -288 4173 -90 -446 -693 4053 -2983 -4783 -305 1723 723 -488 2303 454 3063 2993 -2763 4893 -1123 496 -3813 2143 -2103 -152 -2873 4693 -456 482 2853 -3973 -2783 -116 4953 2733 -1953 -2269 205 1983 3863 -4853 3463 1343 276 -2403 529 -144 -2413 2923 -4323 3923 -4749 3253 563 57 3573 -136 -3893 -699 134 -1323 -3873 -495 3343 -1963 3409 -4903 -1273 -3673 -589 -623 -121 983 669 228 -3073 -222 335 3173 1073 -427 -2319 -4993 -224 321 81 3583 332 4733 -1789 -2083 -486 2099 -471 1113 3773 -879 88 4113 -77 -3399 -3609 -2153 -186 3419 -2093 -462 1943 2743 -3963 412 -1819 4213 -197 322 2903 1719 -2189 2613 -4003 -1216
-4763 400 -4743 -2713 4853 443 483 4313 430 1033 -1663 -345 403 4753 -4543 -1223 382 703 201 -130 25 23 -27 -163 3193 492 18 1123 44 -189 -10 -312 -353 -313 206 179 199 169 -6 -37 4549 35 5 1813 -470 19 -423 -414 -39 93 -21 263 373 45 -266 -2819 -2433 -51 -20 2873 294 -14 -4653 1763 -793 -443 12 -490 -461 -410 719 -362 22 -103 -3353 -223 593 -325 -302 191 -431 -17 120 -24 163 -3069 47 173 -322 -101 -3433 46 13 392 -475 172 -99 -380 -87 -433 -439 38 4933 -122 211 459 -319 31 255 -280 -26 295 -4803 42 -310 -36 -479 -271 -411 -362 333 -166 -283 -3243 -35 237 162 369 -469 -4463 11 -360 4543 -60 100 380 -424 869 -179 -5 -493 -323 3213 -45 21 2633 -46 3523 -420 102 -320 -92 83 -219 -499 -4363 -183 231 -236 -150 -86 383 -355 94 -403 89 161 -245 278 4833 -2543 37 -22 6 -42 230 -131 -391 204 41 -263 3943 80 -169 -393 183 -3253 51 461 -149 -89 3233 24 -109 -1013 34 449 499 4349 17 -3943 -300 -210 26 281 -342 -229 -432 1023 2113 -260 -49 440 1963 -369 -273 129 -28 309 302 376 -913 -220 -274 -226 -4893 203 360 -270 -195 342 391 -82 -141 -4063 -382 -1129 -400 -346 -390 -489 215 282 -16 2133 -440 -2193 351 252 421 -261 401 -38 243 -112 4913 170 999 189 413 -100 -573 -3643 -463 -407 -12 2033 208 -291 -422 -409 -279 -193 -133 519 -330 -239 387 1009 -143 270 4273 393 303 472 225 -435 -450 109 2933 3733 -184 -4633 -48 490 2003 2353 283 430 -4263 241 4163 -4533 236 -365 4253 4063 -4553 -361 -173 -153 4573 -481 1683 493 7 284 381 3293 253 356 432 62 -241 434 123 -84 1313 119 180 389 150 -2493 261 359 140 195 -1543 -383 -72 -395 1363 -2233 -129 299 4843 -4033 -299 4149 -379 -61 450 2563 2413 -372 402 352 -91 683 480 469 -491 -2463 1303 -340 363 -170 -436 -160 -2483 91 -482 -370 305 -243 -4643 121 2849 455 293 3263 3243 1993 4813 -135 372 -93 2333 181 -373 -321 -50 -4919 -343 -3723 313 -1983 110 -1043 -34 -324 -8 3763 -253 4243 131 -3393 -69 1203 -3613 4233 200 79 -2723 395 463 350 -893 -1923 -192 -354 3713 -1693 343 4653 -311 193 -113 -480 -4253 32 -413 254 -196 4873 -392 -341 -351 4249 2453 -3453 2343 73 3853 235 -453 160 220 171 -161 -107 -3773 -217 -74 -1743 -2813 330 -180 -182 -80 -4433 -339 139 -120 291 -3113 -65 280 361 -363 149 -110 -1813 3623 154 -653 -132 -474 167 3053 -415 -123 269 -294 275 184 260 1233 370 -1483 379 339 153 -3473 -1143 913 4453 2299 55 -1423 2013 -293 -371 341 3113 -2113 229 441 -63 -485 92 311 4723 3779 4379 -4623 239 -142 -429 1483 323 -401 -2373 4663 1173 314 135 4503 320 409 -334 -1203 -105 -452 -4833 -199 -421 460 -2163 -543 304 8 479 -1063 -394 355 -221 -2309 -83 -533 -329 3673 2913 219 145 141 -259 -164 -79 -2049 210 -384 -3553 272 -240 1713 190 963 -349 112 -145 -234 257 159 334 -244 -1173 4649 -2523 -2329 301 70 289 3023 -151 -350 142 -465 -2923 2833 -444 -1553 -1623 1513 -3003 72 -381 4553 292 -364 244 -483 415 -419 -3693 -124 -1823 1839 -18 279 63 -3993 2573 192 1703 74 111 3793 -267 -52 -2053 -4123 -4153 130 -4683 3833 399 -4963 -4889 -115 410 329 -1633 259 -139 471 -663 -53 -455 114 3753 76 -3843 249 414 1403 -7 -275 -1263 743 50 -232 3983 -3733 4293 1263 1293 3219 -309 -389 -214 3603 2283 209 344 1543 -3063 -484 -71 274 -2323 673 358 -451 -290 3973 122 -3923 -3273 152 1953 -2973 -4913 -1053 -225 439 -783 -1299 405 3133 -3663 2463 297 -3193 65 -425 2693 2899 452 256 319 226 -3153 -272 -336 -54 470 484 -2383 3883 52 -303 116 -235 371 -4149 -487 -359 4373 -292 4133 -2263 -1333 -96 419 349 -993 1793 -76 -257 221 -3173 -264 3043 643 429 -2733 -211 271 933 -231 -3919 420 -4439 -1863 -256 -3103 -4203 -3803 1573 -366 -464 -4353 -344 494 -70 -106 -2799 1653 -190 -4293 115 82 1433 28 -1683 157 -3413 -643 -434 54 -201 174 59 -3579 125 60 -2903 213 -513 155 326 -2123 -269 354 165 -496 101 234 -254 175 -216 -3143 -304 1523 1883 3279 -306 2673 2753 -285 2263 -563 -137 242 -282 1299 97 442 -347 331 -3483 4773 324 337 -460 -154 4563 4383 -209 105 366 -2943 310 -327 69 -3933 462 4943 -62 -2893 424 -3653 2669 -242 993 -358 -230 437 -140 -181 843 -249 -289 -2029 232 -284 435 -2313 533 3723 -1283 -1113 -2393 -268 398 390 -3329 1603 2269 -1653 -2623 4683 464 1153 4963 1873 315 -863 3453 -3513 251 -1073 186 -1393 3103 290 -252 -4059 406 -251 132 -929 -2513 2683 -2503 136 1753 -386 3903 147 176 265 -441 3503 3703 -1993 64 -2563 -873 2623 -472 456 523 124 -509 2223 -454 -1749 364 411 -352 -2043 1333 2769 -404 -2833 164 1989 543 4623 224 61 431 336 4363 212 -3563 -2303 222 -943 4223 386 -883 -200 -3713 -111 84 -265 -3249 196 3483 2393 -2443 3873 90 -1523 -2343 -4053 -457 -4883 -1453 -1353 -2213 -4233 -308 3303 1773 475 3353 -2913 1863 -1463 -2679 348 -4223 446 -172 -459 4203 2313 -3983 -2553 -3303 444 422 -155 247 -833 -1909 194 -2653 137 4803 -2423 753 -1433 -1713 1553 4709 3563 -374 -3753 -246 -295 -4719 3203 -375 144 287 374 451 3273 -3669 3743 182 312 4809 -763 2273 485 4143 -4283 447 -3123 264 375 -146 -449 -2789 66 -4333 3993 -2919 -1293 -2023 404 -3279 -412 4313 -2643 71 923 345 3633 1163 -1253 -4593 214 -4753 4793 -174 -281 1493 -1153 -2593 -1493 -713 -983 -3089 1833 3533 3143 -3183 1733 340 973 4769 3323 491 -1873 4643 -167 3843 3083 -94 300 -3083 -2273 4763 -1929 202 -162 156 185 -104 -437 67 -288 4173 -90 -446 -693 4053 -2983 -4783 -305 1723 723 -488 2303 454 3063 2993 -2763 4893 -1123 496 -3813 2143 -2103 -152 -2873 4693 -456 482 2853 -3973 -2783 -116 4953 2733 -1953 -2269 205 1983 3863 -4853 3463 1343 276 -2403 529 -144 -2413 2923 -4323 3923 -4749 3253 563 57 3573 -136 -3893 -699 134 -1323 -3873 -495 3343 -1963 3409 -4903 -1273 -3673 -589 -623 -121 983 669 228 -3073 -222 335 3173 1073 -427 -2319 -4993 -224 321 81 3583 332 4733 -1789 -2083 -486 2099 -471 1113 3773 -879 88 4113 -77 -3399 -3609 -2153 -186 3419 -2093 -462 1943 2743 -3963 412 -1819 4213 -197 322 2903 1719 -2189 2613 -4003 -1216

Output

-4993 -4963 -4919 -4913 -4903 -4893 -4889 -4883 -4853 -4833 -4803 -4783 -4763 -4753 -4749 -4743 -4719 -4683 -4653 -4643 -4633 -4623 -4593 -4553 -4543 -4533 -4463 -4439 -4433 -4363 -4353 -4333 -4323 -4293 -4283 -4263 -4253 -4233 -4223 -4203 -4153 -4149 -4123 -4063 -4059 -4053 -4033 -4003 -3993 -3983 -3973 -3963 -3943 -3933 -3923 -3919 -3893 -3873 -3843 -3813 -3803 -3773 -3753 -3733 -3723 -3713 -3693 -3673 -3669 -3663 -3653 -3643 -3613 -3609 -3579 -3563 -3553 -3513 -3483 -3473 -3453 -3433 -3413 -3399 -3393 -3353 -3329 -3303 -3279 -3273 -3253 -3249 -3243 -3193 -3183 -3173 -3153 -3143 -3123 -3113 -3103 -3089 -3083 -3073 -3069 -3063 -3003 -2983 -2973 -2943 -2923 -2919 -2913 -2903 -2893 -2873 -2833 -2819 -2813 -2799 -2789 -2783 -2763 -2733 -2723 -2713 -2679 -2653 -2643 -2623 -2593 -2563 -2553 -2543 -2523 -2513 -2503 -2493 -2483 -2463 -2443 -2433 -2423 -2413 -2403 -2393 -2383 -2373 -2343 -2329 -2323 -2319 -2313 -2309 -2303 -2273 -2269 -2263 -2233 -2213 -2193 -2189 -2163 -2153 -2123 -2113 -2103 -2093 -2083 -2053 -2049 -2043 -2029 -2023 -1993 -1983 -1963 -1953 -1929 -1923 -1909 -1873 -1863 -1823 -1819 -1813 -1789 -1749 -1743 -1713 -1693 -1683 -1663 -1653 -1633 -1623 -1553 -1543 -1523 -1493 -1483 -1463 -1453 -1433 -1423 -1393 -1353 -1333 -1323 -1299 -1293 -1283 -1273 -1263 -1253 -1223 -1216 -1203 -1173 -1153 -1143 -1129 -1123 -1113 -1073 -1063 -1053 -1043 -1013 -993 -983 -943 -929 -913 -893 -883 -879 -873 -863 -833 -793 -783 -763 -713 -699 -693 -663 -653 -643 -623 -589 -573 -563 -543 -533 -513 -509 -499 -496 -495 -493 -491 -490 -489 -488 -487 -486 -485 -484 -483 -482 -481 -480 -479 -475 -474 -472 -471 -470 -469 -465 -464 -463 -462 -461 -460 -459 -457 -456 -455 -454 -453 -452 -451 -450 -449 -446 -444 -443 -441 -440 -439 -437 -436 -435 -434 -433 -432 -431 -429 -427 -425 -424 -423 -422 -421 -420 -419 -415 -414 -413 -412 -411 -410 -409 -407 -404 -403 -401 -400 -395 -394 -393 -392 -391 -390 -389 -386 -384 -383 -382 -381 -380 -379 -375 -374 -373 -372 -371 -370 -369 -366 -365 -364 -363 -362 -361 -360 -359 -358 -355 -354 -353 -352 -351 -350 -349 -347 -346 -345 -344 -343 -342 -341 -340 -339 -336 -334 -330 -329 -327 -325 -324 -323 -322 -321 -320 -319 -313 -312 -311 -310 -309 -308 -306 -305 -304 -303 -302 -300 -299 -295 -294 -293 -292 -291 -290 -289 -288 -285 -284 -283 -282 -281 -280 -279 -275 -274 -273 -272 -271 -270 -269 -268 -267 -266 -265 -264 -263 -261 -260 -259 -257 -256 -254 -253 -252 -251 -249 -246 -245 -244 -243 -242 -241 -240 -239 -236 -235 -234 -232 -231 -230 -229 -226 -225 -224 -223 -222 -221 -220 -219 -217 -216 -214 -211 -210 -209 -201 -200 -199 -197 -196 -195 -193 -192 -190 -189 -186 -184 -183 -182 -181 -180 -179 -174 -173 -172 -170 -169 -167 -166 -164 -163 -162 -161 -160 -155 -154 -153 -152 -151 -150 -149 -146 -145 -144 -143 -142 -141 -140 -139 -137 -136 -135 -133 -132 -131 -130 -129 -124 -123 -122 -121 -120 -116 -115 -113 -112 -111 -110 -109 -107 -106 -105 -104 -103 -101 -100 -99 -96 -94 -93 -92 -91 -90 -89 -87 -86 -84 -83 -82 -80 -79 -77 -76 -74 -72 -71 -70 -69 -65 -63 -62 -61 -60 -54 -53 -52 -51 -50 -49 -48 -46 -45 -42 -39 -38 -37 -36 -35 -34 -28 -27 -26 -24 -22 -21 -20 -18 -17 -16 -14 -12 -10 -8 -7 -6 -5 5 6 7 8 11 12 13 17 18 19 21 22 23 24 25 26 28 31 32 34 35 37 38 41 42 44 45 46 47 50 51 52 54 55 57 59 60 61 62 63 64 65 66 67 69 70 71 72 73 74 76 79 80 81 82 83 84 88 89 90 91 92 93 94 97 100 101 102 105 109 110 111 112 114 115 116 119 120 121 122 123 124 125 129 130 131 132 134 135 136 137 139 140 141 142 144 145 147 149 150 152 153 154 155 156 157 159 160 161 162 163 164 165 167 169 170 171 172 173 174 175 176 179 180 181 182 183 184 185 186 189 190 191 192 193 194 195 196 199 200 201 202 203 204 205 206 208 209 210 211 212 213 214 215 219 220 221 222 224 225 226 228 229 230 231 232 234 235 236 237 239 241 242 243 244 247 249 251 252 253 254 255 256 257 259 260 261 263 264 265 269 270 271 272 274 275 276 278 279 280 281 282 283 284 287 289 290 291 292 293 294 295 297 299 300 301 302 303 304 305 309 310 311 312 313 314 315 319 320 321 322 323 324 326 329 330 331 332 333 334 335 336 337 339 340 341 342 343 344 345 348 349 350 351 352 354 355 356 358 359 360 361 363 364 366 369 370 371 372 373 374 375 376 379 380 381 382 383 386 387 389 390 391 392 393 395 398 399 400 401 402 403 404 405 406 409 410 411 412 413 414 415 419 420 421 422 424 429 430 431 432 434 435 437 439 440 441 442 443 444 446 447 449 450 451 452 454 455 456 459 460 461 462 463 464 469 470 471 472 475 479 480 482 483 484 485 490 491 492 493 494 496 499 519 523 529 533 543 563 593 643 669 673 683 703 719 723 743 753 843 869 913 923 933 963 973 983 993 999 1009 1023 1033 1073 1113 1123 1153 1163 1173 1203 1233 1263 1293 1299 1303 1313 1333 1343 1363 1403 1433 1483 1493 1513 1523 1543 1553 1573 1603 1653 1683 1703 1713 1719 1723 1733 1753 1763 1773 1793 1813 1833 1839 1863 1873 1883 1943 1953 1963 1983 1989 1993 2003 2013 2033 2099 2113 2133 2143 2223 2263 2269 2273 2283 2299 2303 2313 2333 2343 2353 2393 2413 2453 2463 2563 2573 2613 2623 2633 2669 2673 2683 2693 2733 2743 2753 2769 2833 2849 2853 2873 2899 2903 2913 2923 2933 2993 3023 3043 3053 3063 3083 3103 3113 3133 3143 3173 3193 3203 3213 3219 3233 3243 3253 3263 3273 3279 3293 3303 3323 3343 3353 3409 3419 3453 3463 3483 3503 3523 3533 3563 3573 3583 3603 3623 3633 3673 3703 3713 3723 3733 3743 3753 3763 3773 3779 3793 3833 3843 3853 3863 3873 3883 3903 3923 3943 3973 3983 3993 4053 4063 4113 4133 4143 4149 4163 4173 4203 4213 4223 4233 4243 4249 4253 4273 4293 4313 4349 4363 4373 4379 4383 4453 4503 4543 4549 4553 4563 4573 4623 4643 4649 4653 4663 4683 4693 4709 4723 4733 4753 4763 4769 4773 4793 4803 4809 4813 4833 4843 4853 4873 4893 4913 4933 4943 4953 4963 
BST suficient balancejat

Information

Author: Jordi Esteve
Language: Catalan
Official solutions: C++
User solutions: C++