8 2 1000000000
6 2 148370906
1 5 284327993
8 1 863129040
1 2 878211568
2 4 233310787
7 3 562520178
3 2 329048348