{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"challenge_problem_statement\"\u003e\u003cdiv class\u003d\"msB challenge_problem_statement_body\"\u003e\u003cdiv class\u003d\"hackdown-content\"\u003e\u003cstyle id\u003d\"MathJax_SVG_styles\"\u003e.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%}\n.MathJax_SVG .MJX-monospace {font-family: monospace}\n.MathJax_SVG .MJX-sans-serif {font-family: sans-serif}\n.MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0}\n.MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none}\n.mjx-svg-href {fill: blue; stroke: blue}\n\u003c/style\u003e\u003csvg style\u003d\"display: none;\"\u003e\u003cdefs id\u003d\"MathJax_SVG_glyphs\"\u003e\u003c/defs\u003e\u003c/svg\u003e\u003cp\u003eYou are given a \u003ca href\u003d\"https://en.wikipedia.org/wiki/Tree_%28graph_theory%29\"\u003etree\u003c/a\u003e with N nodes and each has a value associated with it. You are given Q queries, each of which is either an update or a retrieval operation. \u003c/p\u003e\n\n\u003cp\u003eInitially all node values are zero. \u003c/p\u003e\n\n\u003cp\u003eThe \u003cstrong\u003eupdate query\u003c/strong\u003e is of the format\u003c/p\u003e\n\n\u003cpre\u003e\u003ccode\u003ea1 d1 a2 d2 A B\n\u003c/code\u003e\u003c/pre\u003e\n\n\u003cp\u003eThis means you\u0027d have to add \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-1-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"32.561ex\" height\u003d\"2.843ex\" style\u003d\"vertical-align: -0.838ex;\" viewBox\u003d\"0 -863.1 14019.4 1223.9\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(389,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(919,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(1641,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(2642,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(3333,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M229 286Q216 420 216 436Q216 454 240 464Q241 464 245 464T251 465Q263 464 273 456T283 436Q283 419 277 356T270 286L328 328Q384 369 389 372T399 375Q412 375 423 365T435 338Q435 325 425 315Q420 312 357 282T289 250L355 219L425 184Q434 175 434 161Q434 146 425 136T401 125Q393 125 383 131T328 171L270 213Q283 79 283 63Q283 53 276 44T250 35Q231 35 224 44T216 63Q216 80 222 143T229 213L171 171Q115 130 110 127Q106 124 100 124Q87 124 76 134T64 161Q64 166 64 169T67 175T72 181T81 188T94 195T113 204T138 215T170 230T210 250L74 315Q65 324 65 338Q65 353 74 363T98 374Q106 374 116 368T171 328L229 286Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(4055,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M366 683Q367 683 438 688T511 694Q523 694 523 686Q523 679 450 384T375 83T374 68Q374 26 402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487H491Q506 153 506 145Q506 140 503 129Q490 79 473 48T445 8T417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157Q33 205 53 255T101 341Q148 398 195 420T280 442Q336 442 364 400Q369 394 369 396Q370 400 396 505T424 616Q424 629 417 632T378 637H357Q351 643 351 645T353 664Q358 683 366 683ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(4579,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M213 578L200 573Q186 568 160 563T102 556H83V602H102Q149 604 189 617T245 641T273 663Q275 666 285 666Q294 666 302 660V361L303 61Q310 54 315 52T339 48T401 46H427V0H416Q395 3 257 3Q121 3 100 0H88V46H114Q136 46 152 46T177 47T193 50T201 52T207 57T213 61V578Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(5079,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(5691,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M229 286Q216 420 216 436Q216 454 240 464Q241 464 245 464T251 465Q263 464 273 456T283 436Q283 419 277 356T270 286L328 328Q384 369 389 372T399 375Q412 375 423 365T435 338Q435 325 425 315Q420 312 357 282T289 250L355 219L425 184Q434 175 434 161Q434 146 425 136T401 125Q393 125 383 131T328 171L270 213Q283 79 283 63Q283 53 276 44T250 35Q231 35 224 44T216 63Q216 80 222 143T229 213L171 171Q115 130 110 127Q106 124 100 124Q87 124 76 134T64 161Q64 166 64 169T67 175T72 181T81 188T94 195T113 204T138 215T170 230T210 250L74 315Q65 324 65 338Q65 353 74 363T98 374Q106 374 116 368T171 328L229 286Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(6414,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M94 250Q94 319 104 381T127 488T164 576T202 643T244 695T277 729T302 750H315H319Q333 750 333 741Q333 738 316 720T275 667T226 581T184 443T167 250T184 58T225 -81T274 -167T316 -220T333 -241Q333 -250 318 -250H315H302L274 -226Q180 -141 137 -14T94 250Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(6803,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M33 157Q33 258 109 349T280 441Q331 441 370 392Q386 422 416 422Q429 422 439 414T449 394Q449 381 412 234T374 68Q374 43 381 35T402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487Q506 153 506 144Q506 138 501 117T481 63T449 13Q436 0 417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157ZM351 328Q351 334 346 350T323 385T277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q217 26 254 59T298 110Q300 114 325 217T351 328Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(7333,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(8056,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M56 237T56 250T70 270H369V420L370 570Q380 583 389 583Q402 583 409 568V270H707Q722 262 722 250T707 230H409V-68Q401 -82 391 -82H389H387Q375 -82 369 -68V230H70Q56 237 56 250Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(9056,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(9747,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M229 286Q216 420 216 436Q216 454 240 464Q241 464 245 464T251 465Q263 464 273 456T283 436Q283 419 277 356T270 286L328 328Q384 369 389 372T399 375Q412 375 423 365T435 338Q435 325 425 315Q420 312 357 282T289 250L355 219L425 184Q434 175 434 161Q434 146 425 136T401 125Q393 125 383 131T328 171L270 213Q283 79 283 63Q283 53 276 44T250 35Q231 35 224 44T216 63Q216 80 222 143T229 213L171 171Q115 130 110 127Q106 124 100 124Q87 124 76 134T64 161Q64 166 64 169T67 175T72 181T81 188T94 195T113 204T138 215T170 230T210 250L74 315Q65 324 65 338Q65 353 74 363T98 374Q106 374 116 368T171 328L229 286Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(10470,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M366 683Q367 683 438 688T511 694Q523 694 523 686Q523 679 450 384T375 83T374 68Q374 26 402 26Q411 27 422 35Q443 55 463 131Q469 151 473 152Q475 153 483 153H487H491Q506 153 506 145Q506 140 503 129Q490 79 473 48T445 8T417 -8Q409 -10 393 -10Q359 -10 336 5T306 36L300 51Q299 52 296 50Q294 48 292 46Q233 -10 172 -10Q117 -10 75 30T33 157Q33 205 53 255T101 341Q148 398 195 420T280 442Q336 442 364 400Q369 394 369 396Q370 400 396 505T424 616Q424 629 417 632T378 637H357Q351 643 351 645T353 664Q358 683 366 683ZM352 326Q329 405 277 405Q242 405 210 374T160 293Q131 214 119 129Q119 126 119 118T118 106Q118 61 136 44T179 26Q233 26 290 98L298 109L352 326Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(10993,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M109 429Q82 429 66 447T50 491Q50 562 103 614T235 666Q326 666 387 610T449 465Q449 422 429 383T381 315T301 241Q265 210 201 149L142 93L218 92Q375 92 385 97Q392 99 409 186V189H449V186Q448 183 436 95T421 3V0H50V19V31Q50 38 56 46T86 81Q115 113 136 137Q145 147 170 174T204 211T233 244T261 278T284 308T305 340T320 369T333 401T340 431T343 464Q343 527 309 573T212 619Q179 619 154 602T119 569T109 550Q109 549 114 549Q132 549 151 535T170 489Q170 464 154 447T109 429Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(11494,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M60 749L64 750Q69 750 74 750H86L114 726Q208 641 251 514T294 250Q294 182 284 119T261 12T224 -76T186 -143T145 -194T113 -227T90 -246Q87 -249 86 -250H74Q66 -250 63 -250T58 -247T55 -238Q56 -237 66 -225Q221 -64 221 250T66 725Q56 737 55 738Q55 746 60 749Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(12105,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M229 286Q216 420 216 436Q216 454 240 464Q241 464 245 464T251 465Q263 464 273 456T283 436Q283 419 277 356T270 286L328 328Q384 369 389 372T399 375Q412 375 423 365T435 338Q435 325 425 315Q420 312 357 282T289 250L355 219L425 184Q434 175 434 161Q434 146 425 136T401 125Q393 125 383 131T328 171L270 213Q283 79 283 63Q283 53 276 44T250 35Q231 35 224 44T216 63Q216 80 222 143T229 213L171 171Q115 130 110 127Q106 124 100 124Q87 124 76 134T64 161Q64 166 64 169T67 175T72 181T81 188T94 195T113 204T138 215T170 230T210 250L74 315Q65 324 65 338Q65 353 74 363T98 374Q106 374 116 368T171 328L229 286Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003cg transform\u003d\"translate(12828,0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M230 637Q203 637 198 638T193 649Q193 676 204 682Q206 683 378 683Q550 682 564 680Q620 672 658 652T712 606T733 563T739 529Q739 484 710 445T643 385T576 351T538 338L545 333Q612 295 612 223Q612 212 607 162T602 80V71Q602 53 603 43T614 25T640 16Q668 16 686 38T712 85Q717 99 720 102T735 105Q755 105 755 93Q755 75 731 36Q693 -21 641 -21H632Q571 -21 531 4T487 82Q487 109 502 166T517 239Q517 290 474 313Q459 320 449 321T378 323H309L277 193Q244 61 244 59Q244 55 245 54T252 50T269 48T302 46H333Q339 38 339 37T336 19Q332 6 326 0H311Q275 2 180 2Q146 2 117 2T71 2T50 1Q33 1 33 10Q33 12 36 24Q41 43 46 45Q50 46 61 46H67Q94 46 127 49Q141 52 146 61Q149 65 218 339T287 628Q287 635 230 637ZM630 554Q630 586 609 608T523 636Q521 636 500 636T462 637H440Q393 637 386 627Q385 624 352 494T319 361Q319 360 388 360Q466 361 492 367Q556 377 592 426Q608 449 619 486T630 554Z\"\u003e\u003c/path\u003e\u003cg transform\u003d\"translate(759,362)\"\u003e\u003cpath stroke-width\u003d\"1\" transform\u003d\"scale(0.707)\" d\u003d\"M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/g\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e in all nodes in the path from A to B where \u003cspan style\u003d\"font-size: 100%; display: inline-block;\" class\u003d\"MathJax_SVG\" id\u003d\"MathJax-Element-2-Frame\"\u003e\u003csvg xmlns:xlink\u003d\"http://www.w3.org/1999/xlink\" width\u003d\"1.088ex\" height\u003d\"1.676ex\" style\u003d\"vertical-align: -0.338ex;\" viewBox\u003d\"0 -576.1 468.5 721.6\" role\u003d\"img\" focusable\u003d\"false\"\u003e\u003cg stroke\u003d\"currentColor\" fill\u003d\"currentColor\" stroke-width\u003d\"0\" transform\u003d\"matrix(1 0 0 -1 0 0)\"\u003e\u003cpath stroke-width\u003d\"1\" d\u003d\"M347 338Q337 338 294 349T231 360Q211 360 197 356T174 346T162 335T155 324L153 320Q150 317 138 317Q117 317 117 325Q117 330 120 339Q133 378 163 406T229 440Q241 442 246 442Q271 442 291 425T329 392T367 375Q389 375 411 408T434 441Q435 442 449 442H462Q468 436 468 434Q468 430 463 420T449 399T432 377T418 358L411 349Q368 298 275 214T160 106L148 94L163 93Q185 93 227 82T290 71Q328 71 360 90T402 140Q406 149 409 151T424 153Q443 153 443 143Q443 138 442 134Q425 72 376 31T278 -11Q252 -11 232 6T193 40T155 57Q111 57 76 -3Q70 -11 59 -11H54H41Q35 -5 35 -2Q35 13 93 84Q132 129 225 214T340 322Q352 338 347 338Z\"\u003e\u003c/path\u003e\u003c/g\u003e\u003c/svg\u003e\u003c/span\u003e is the distance between the node and A.\u003c/p\u003e\n\n\u003cp\u003eThe \u003cstrong\u003eretrieval\u003c/strong\u003e query is of the format\u003c/p\u003e\n\n\u003cpre\u003e\u003ccode\u003ei j\n\u003c/code\u003e\u003c/pre\u003e\n\n\u003cp\u003eYou need to return the sum of the node values lying in the path from node i to node j modulo 1000000007. \u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eNote\u003c/strong\u003e: \u003c/p\u003e\n\n\u003col\u003e\n\u003cli\u003eFirst all update queries are given and then all retrieval queries. \u003c/li\u003e\n\u003cli\u003eDistance between 2 nodes is the shortest path length between them taking each edge weight as 1. \u003c/li\u003e\n\u003c/ol\u003e\n\n\u003cp\u003e\u003cstrong\u003eInput Format\u003c/strong\u003e \u003c/p\u003e\n\n\u003cp\u003eThe first line contains two integers (N and R respectively) separated by a space. \u003c/p\u003e\n\n\u003cp\u003eIn the next N-1 lines, the i\u003csup\u003eth\u003c/sup\u003e line describes the i\u003csup\u003eth\u003c/sup\u003e edge: a line with two integers x y separated by a single space denotes an edge between nodes x and y. \u003c/p\u003e\n\n\u003cp\u003eThe next line contains 2 space separated integers (U and Q respectively) representing the number of Update and Query operations to follow. \u003c/p\u003e\n\n\u003cp\u003eU lines follow. Each of the next U lines contains 6 space separated integers (a1,d1,a2,d2,A and B respectively).\u003c/p\u003e\n\n\u003cp\u003eEach of the next Q lines contains 2 space separated integers, i and j respectively. \u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eOutput Format\u003c/strong\u003e \u003c/p\u003e\n\n\u003cp\u003eIt contains exactly Q lines and each line containing the answer of the i\u003csup\u003eth\u003c/sup\u003e query.\u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eConstraints\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003e2 \u0026lt;\u003d N \u0026lt;\u003d 10\u003csup\u003e5\u003c/sup\u003e \u003cbr\u003e\n2 \u0026lt;\u003d R \u0026lt;\u003d 10\u003csup\u003e9\u003c/sup\u003e \u003cbr\u003e\n1 \u0026lt;\u003d U \u0026lt;\u003d 10\u003csup\u003e5\u003c/sup\u003e \u003cbr\u003e\n1 \u0026lt;\u003d Q \u0026lt;\u003d 10\u003csup\u003e5\u003c/sup\u003e \u003cbr\u003e\n1 \u0026lt;\u003d a1,a2,d1,d2 \u0026lt;\u003d 10\u003csup\u003e8\u003c/sup\u003e \u003cbr\u003e\n1 \u0026lt;\u003d x, y, i, j, A, B \u0026lt;\u003d N \u003c/p\u003e\n\n\u003cp\u003e\u003cstrong\u003eNote\u003c/strong\u003e \u003cbr\u003e\nFor the update operation, x can be equal to y and for the query operation, i can be equal to j. \u003c/p\u003e\n\n\u003cdiv\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 2\n1 2\n1 3\n2 4\n2 6\n4 5\n6 7\n1 4\n1 1 1 1 4 6\n4 5\n2 7\n4 7\n5 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n44\n45\n9\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\n\n\n\n\n\n\n\u003cp\u003e\u003cstrong\u003eExplanation\u003c/strong\u003e\u003c/p\u003e\n\n\u003cp\u003eThe node values after updation becomes : \u003c/p\u003e\n\n\u003cpre\u003e\u003ccode\u003e0 8 0 1 0 36 0\n\u003c/code\u003e\u003c/pre\u003e\n\n\u003cp\u003eAnswer to Query #1: 1+0 \u003d 1 \u003c/p\u003e\n\n\u003cp\u003eAnswer to Query #2: 8+36+0 \u003d 44\u003c/p\u003e\n\n\u003cp\u003eAnswer to Query #3: 1+8+36+0 \u003d 45\u003c/p\u003e\n\n\u003cp\u003eAnswer to Query #4: 0+1+8+0+0 \u003d 9\u003c/p\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e"}}]}