Input
2
6 2
1 2
Output
6 6
Input
3
6 2 3
1 2
1 3
Output
6 6 6
Input
1
10
Output
10