4 3 -1 1 2 1000000 1 500000 1000 577 87517 627 348023 660 38166 -1 -1 -1 40554 452 452 998 5982 1195 4757 6656 45609 9789 7223 -1 10700 81 39 -1 67