3236 - [Ahoi2013]作业

Input

Output

Examples

Input

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

Output

2 2
1 1
3 2
2 1

Hint

N=100000,M=1000000

Time Limit 3 seconds
Memory Limit 128 MB
Stats
上一题 下一题