1 2147483647 2147483647 2 1 20 3 35 55 4 1 1 5 20 1 6 1000001 1200000 7 1000000 1000000 8 2000000 2000000 9 4000000 4000000 10 2147483647 2147483647 11 16 16 12 1 2 13 58 58 14 19 19 15 1 3 16 1 2 17 2 2 18 1 2 19 1 10000 20 30000 100000 21 1 1000000 22 42 18 23 35 1 24 20 25 25 29 9 26 13 15 27 6 46 28 32 28 29 12 42 30 46 43 31 28 37 32 42 5 33 3 4 34 43 33 35 22 17 36 19 46 37 48 27 38 22 39 39 20 13 40 18 50 41 36 45 42 0 0 43