Previous View Logs Next
Ticket 4293
Problem 1661 -e
Submission 153233012
View hacks & all small testcases

Unable to dry run this testcase?
Try making a new request with small values of n_high, t_high, *_high, etc.


Retry
Input
5
11111
10001
11011
10000
2 4
4 5
2 2
2 3
2 2
1 2
1 4
3 3
2 3
1 4
1 2
3 3
1 5
3 5
4 5
4 4
1 5
5 5
1 5
2 3
5 5
1 3
1 2
2 4
2 4
1 4
4 4
2 4
1 3
2 5
3 5
3 3
5 5
1 3
1 4
1 5
2 3
2 3
2 5
3 4
2 3
4 5
3 4
1 3
1 1
2 2
5 5
2 5
2 3
4 5
1 3
4 5
1 2
1 5
2 2
1 4
3 3
3 4
1 3
1 5
4 5
1 4
1 2
1 2
2 2
5 5
1 5
2 3
4 5
1 5
1 4
4 5
2 4
2 4
2 3
4 4
5 5
2 5
4 5
2 4
1 3
2 5
1 5
3 5
3 4
2 5
1 3
3 4
1 2
1 2
1 5
2 5
2 5
4 5
1 4
3 5
1 4
3 5
3 4
2 4
1 4
3 5
5 5
3 5
4 5
2 4
3 4
1 2
4 5
1 3
2 5
1 2
4 5
1 3
3 4
4 4
3 4
2 2
3 5
1 4
5 5
2 3
1 3
1 5
2 3
2 5
3 4
2 3
3 5
3 5
3 5
1 5
1 3
3 4
2 4
2 2
2 2
2 3
3 3
4 4
1 4
2 2
1 4
4 5
2 4
3 5
1 4
3 3
4 5
3 4
1 5
3 5
3 5
3 4
2 5
2 4
2 4
1 4
2 4
3 3
5 5
5 5
3 5
1 5
1 2
3 4
1 2
1 2
4 5
2 4
3 5
3 5
2 5
2 4
2 5
1 2
3 4
3 3
1 3
3 5
1 4
3 5
1 1
1 1
2 5
3 5
3 4
4 5
2 4
3 3
3 4
1 1
2 5
1 3
2 4
4 4
1 3
1 4
1 5
1 5
1 5
4 5
1 1
1 1
1 3
4 4
1 4
1 4
1 5
2 3
1 3
3 3
3 3
3 5
1 3
1 5
1 2
3 4
3 4
3 4
2 4
3 4
1 1
1 3
1 3
1 3
2 3
2 4
2 2
2 4
5 5
1 5
1 4
5 5
2 3
2 3
2 2
2 4
1 2
4 5
2 5
1 5
1 3
1 4
2 2
2 3
3 3
3 5
2 4
2 5
1 4
3 5
1 3
3 4
2 4
1 1
1 4
3 5
1 5
1 2
2 5
3 5
2 5
2 4
1 2
1 5
3 4
2 2
3 5
2 5
1 5
4 5
2 4
4 4
4 5
4 5
4 4
2 5
2 2
1 3
3 4
1 2
5 5
4 5
2 4
4 5
1 4
1 3
2 5
4 4
4 5
3 5
3 5
1 3
1 3
1 2
2 3
2 5
1 3
1 3
1 3
1 3
1 2
5 5
1 3
4 5
1 1
5 5
2 4
4 5
4 5
1 3
2 3
3 5
2 5
3 4
4 4
2 3
1 2
5 5
1 3
4 4
3 4
3 5
4 5
2 3
3 4
1 4
3 3
3 5
1 5
5 5
2 5
3 4
2 5
1 1
2 2
3 4
1 2
1 2
1 2
1 3
5 5
1 2
1 4
4 5
3 4
2 5
2 5
3 4
5 5
1 3
1 4
2 3
1 3
3 4
1 2
2 4
1 1
2 5
3 4
2 3
1 2
2 3
4 4
4 4
4 5
2 5
3 4
3 5
1 5
4 4
3 5
1 2
3 4
3 5
1 3
2 3
1 4
3 5
5 5
2 3
2 3
2 3
1 4
3 4
2 2
2 2
2 5
2 4
3 4
1 4
1 2
1 3
5 5
2 4
2 5
1 5
3 4
2 4
4 4
2 3
4 5
1 5
2 3
2 2
1 3
2 4
1 5
2 4
1 4
1 2
1 5
3 5
1 3
4 4
2 4
2 5
3 3
1 4
2 4
1 4
1 5
1 4
3 3
3 5
1 5
3 4
2 4
4 5
3 4
1 5
1 2
3 3
2 3
2 4
1 4
2 3
4 5
1 2
5 5
3 4
2 3
1 3
1 4
1 5
2 5
1 3
3 4
2 4
3 5
2 5
3 5
3 4
1 4
2 4
1 5
1 3
2 3
1 4
1 4
3 5
1 3
3 4
2 4
3 4
1 4
4 5
1 3
1 3
3 5
3 4
2 4
1 2
3 5
2 3
2 5
2 5
1 3
1 5
3 4
2 4
1 4
1 5
2 3
2 3
5 5
3 3
3 3
1 5
2 5
2 3
2 4
1 5
4 5
1 4
4 5
1 1
2 5
1 4
1 3
2 5
2 3
4 4
4 4
1 4
1 5
5 5
3 4
1 3
3 5
1 2
1 3
3 3
1 2
3 5
1 5
2 3
2 5
4 5
3 5
1 5
1 3
1 5
4 4
3 5
5 5
1 5
2 5
3 3
1 3
3 5
3 4
1 3
4 4
1 5
1 4
4 5
2 3
2 2
4 4
1 2
3 4
2 3
1 4
1 5
1 4
2 2
2 2
1 5
3 4
2 3
3 4
1 4
3 5
1 2
4 5
1 2
2 5
3 4
1 4
1 4
2 2
1 5
2 5
1 2
4 4
3 5
2 4
4 5
2 5
4 4
1 2
2 4
2 4
5 5
5 5
4 5
3 4
1 3
3 3
2 4
3 4
1 5
2 4
4 5
1 3
1 5
1 2
1 3
2 4
1 3
2 3
5 5
1 2
1 4
1 4
4 5
1 5
1 2
5 5
1 5
3 4
3 5
1 5
4 4
1 3
1 1
2 4
2 3
1 3
2 4
3 3
2 3
1 3
4 5
3 4
2 3
4 4
3 3
2 4
1 5
1 1
3 5
1 5
2 4
1 4
4 5
1 2
2 2
3 3
1 2
1 4
5 5
4 4
4 5
1 5
1 1
2 4
1 3
1 4
1 2
5 5
5 5
1 2
2 3
4 5
2 5
2 4
4 4
1 2
3 5
3 4
3 4
2 5
1 5
3 4
4 4
2 5
5 5
4 5
4 4
1 5
1 3
3 3
1 2
2 4
3 5
3 5
2 4
3 5
2 4
3 4
1 2
3 5
4 4
2 3
4 5
2 4
2 4
4 5
2 2
1 1
2 5
3 4
1 3
2 4
2 4
1 2
2 5
1 3
1 2
1 2
4 4
2 4
5 5
2 3
1 5
2 5
3 5
3 3
5 5
1 4
1 5
1 2
4 5
1 1
4 5
4 5
3 5
2 5
2 2
1 2
2 3
3 3
1 4
2 5
3 4
4 5
2 3
4 5
5 5
3 5
1 3
2 5
1 5
3 5
1 2
2 3
3 4
3 3
2 3
2 3
1 5
2 2
1 5
3 3
2 5
3 5
3 5
1 1
1 2
3 4
2 4
3 4
2 5
2 5
1 3
4 5
3 5
1 1
3 3
3 5
1 1
5 5
3 4
2 3
4 5
2 2
2 3
2 5
1 2
3 5
4 5
2 4
4 4
1 3
2 4
1 3
3 5
3 5
4 5
4 5
2 4
3 5
3 5
1 1
3 5
1 2
5 5
2 5
2 2
4 5
2 5
2 3
2 2
3 4
2 5
2 2
2 3
5 5
1 5
2 4
3 5
1 5
2 3
1 4
2 2
3 4
1 2
3 3
3 5
1 2
3 5
4 5
2 3
1 2
2 5
4 5
2 3
4 5
1 2
2 5
2 5
1 5
1 2
1 5
1 5
3 3
1 3
1 1
3 5
1 4
1 5
3 4
3 3
2 5
3 5
2 3
1 5
2 3
1 4
1 5
1 5
1 4
2 3
3 4
2 3
2 3
3 5
2 5
1 3
3 5
1 3
3 5
2 5
3 5
5 5
1 2
3 4
1 4
3 4
5 5
1 4
1 3
2 5
2 5
3 5
1 3
1 5
2 4
2 4
3 5
4 5
2 2
1 5
1 4
4 5
2 3
1 1
1 3
3 4
1 5
2 5
1 2
2 4
2 3
1 5
3 5
1 2
1 5
3 4
4 5
2 4
3 5
2 2
1 4
2 5
2 3
1 5
1 2
2 2
1 2
1 5
3 4
2 4
2 2
2 5
1 3
2 5
2 4
1 5
3 5
3 4
1 3
4 4
1 4
1 2
1 4
1 5
3 5
2 2
3 4
5 5
5 5
3 3
2 3
1 5
5 5
2 5
4 5
2 2
1 4
1 4
1 3
1 1
4 4
1 1
5 5
1 3
1 3
1 5
3 5
2 3
1 1
2 4
3 5
1 2
1 5
4 5
3 5
4 4
3 5
2 5
2 3
5 5
3 4
2 4
1 2
4 4
3 3
2 4
1 5
1 2
3 3
3 4
1 2
4 5
3 5
2 3
1 3
1 2
2 3
2 3
2 5
3 4
1 2
2 4
2 4
2 2
2 4
5 5
2 2
2 2
2 3
1 3
2 4
1 4
5 5
1 5
2 3
2 5
4 4
4 5
1 4
1 2
3 5
2 4
3 3
4 5
1 4
5 5
4 5
1 2
2 2
2 4
3 5
1 3
3 4
2 4
1 5
2 5
1 5
2 5
1 4
1 2
3 5
1 4
4 4
2 3
2 3
2 5
3 5
1 3
1 5
4 5
1 2
2 5
2 4
3 4
1 1
1 4
5 5
1 3
4 5
2 5
3 5
2 4
4 4
1 5
1 5
3 4
2 2
4 5
1 4
2 4
4 5
1 5
1 3
2 3
5 5
2 5
1 3
2 3
1 4
1 4
1 4
3 3
1 2
3 5
1 1
2 5
1 5
3 4
4 4
3 5
1 2
2 3
3 3
4 4
3 3
2 5
2 3
1 4
2 2
1 4
2 4
4 5
1 3
3 4
2 3
2 3
2 4
1 4
1 4
2 2
1 4
5 5
2 4
2 3
1 3
1 5
1 4
2 3
2 5
3 4
2 2
4 4
1 3
2 3
2 3
1 3
1 3
3 4
2 3
1 3
3 4
1 5
1 4
4 5
1 2
2 4
2 5
1 4
1 4
2 4
3 4
1 3
2 3
3 5
1 4
2 3
1 2
4 5
1 3
3 3
1 2
3 4
1 3
1 2
5 5
4 5
3 3
3 4
3 4
2 3
2 5
2 4
1 2
1 2
1 5
3 5
3 5
3 5
4 5
3 5
5 5
4 4
5 5
1 4
1 5
1 5
4 4
1 4
2 4
2 5
1 5
3 5
3 4
1 5
1 2
4 5
2 4
1 5
1 1
2 3
1 4
2 4
3 3
3 4
2 2
3 3
1 3
2 4
2 2
2 3
2 3
3 5
1 2
4 5
5 5
2 5
4 5
2 2
1 5
4 5
1 2
2 5
1 5
4 5
1 5
1 4
2 5
4 5
2 5
3 5
3 4
2 2
4 5
2 4
3 4
3 3
1 4
3 5
4 5
4 5
4 5
3 3
1 5
2 4
5 5
3 5
3 5
1 4
2 4
3 3
2 5
2 2
1 3
3 4
1 2
1 3
3 4
4 4
1 2
1 2
1 1
2 3
2 3
2 3
4 5
4 5
4 5
4 5
1 3
2 3
3 4
5 5
1 5
2 3
2 4
4 4
5 5
4 5
2 5
2 4
2 3
2 4
2 4
4 4
5 5
1 4
3 5
3 5
4 4
4 5
2 5
2 2
1 2
1 4
1 2
4 5
2 3
4 5
1 3
1 4
1 2
2 3
1 4
5 5
1 2
3 4
2 4
4 4
1 5
4 4
3 4
2 5
3 3
3 3
4 5
2 4
2 2
1 3
3 3
3 5
4 4
1 2
1 4
3 5
1 4
1 5
3 4
1 2
2 3
2 4
1 3
3 3
3 3
3 3
1 4
1 4
1 2
3 4
4 5
1 3
3 5
4 5
3 4
3 3
3 5
2 2
2 4
1 2
2 4
1 4
2 2
3 4
1 2
2 2
3 4
1 3
4 4
2 3
3 4
2 2
1 2
2 5
2 2
2 5
3 4
2 3
1 1
2 4
2 4
2 3
4 5
4 5
4 4
3 3
1 2
2 2
1 1
1 1
1 3
1 3
3 5
4 5
1 5
2 5
4 5
3 4
4 5
1 5
4 5
4 4
1 5
3 4
4 5
2 5
2 3
1 5
2 2
3 4
1 4
3 5
1 2
4 5
1 5
1 4
3 5
2 4
2 4
1 1
2 4
1 2
3 4
3 4
3 4
2 3
2 3
3 4
3 3
2 3
1 3
2 4
3 4
1 4
3 5
2 4
4 5
1 3
3 4
3 4
2 5
2 5
1 5
3 5
2 3
2 5
2 3
1 2
1 5
4 4
3 3
1 3
1 2
1 2
1 1
2 5
3 3
1 1
2 5
1 3
1 3
1 4
2 4
2 4
1 2
2 4
1 4
2 5
2 3
3 4
2 4
1 2
2 5
1 4
2 4
1 2
2 4
2 5
3 5
2 4
1 1
4 5
1 5
2 3
1 4
1 1
1 4
4 5
1 3
1 4
1 5
5 5
2 5
2 5
2 5
3 4
3 4
4 5
2 5
2 4
3 5
4 5
1 2
3 5
2 4
3 3
1 2
2 3
2 4
1 3
3 4
3 4
2 4
3 5
1 3
2 3
1 3
5 5
1 4
1 5
4 4
4 4
3 3
2 4
2 5
4 5
1 3
4 4
2 5
1 2
1 5
1 4
4 5
1 5
3 5
4 5
1 2
4 5
2 5
1 4
1 3
4 5
4 5
2 5
1 5
1 3
3 4
1 4
5 5
4 5
3 4
4 4
5 5
4 4
2 5
1 5
1 1
3 4
2 4
3 4
4 5
3 5
3 5
1 5
3 4
1 2
4 4
1 1
1 5
1 5
1 2
1 1
3 3
3 4
1 5
3 5
5 5
3 5
1 5
2 5
2 5
5 5
3 5
1 2
1 4
3 4
4 5
1 1
4 4
1 5
1 2
2 5
2 2
1 5
2 5
1 5
2 4
1 1
1 4
4 5
4 4
2 3
4 5
1 1
5 5
1 1
2 4
5 5
2 4
3 4
1 2
2 5
3 5
4 4
1 4
3 5
3 3
1 5
4 4
2 5
4 4
1 2
1 5
1 3
2 5
2 5
3 5
4 4
2 4
1 3
4 4
2 4
1 3
1 3
3 5
1 1
1 4
2 4
1 3
2 5
1 3
1 3
1 4
1 3
4 5
2 2
1 4
3 5
1 4
2 4
1 5
1 3
3 5
2 4
3 5
4 5
1 3
1 3
2 2
5 5
2 3
3 4
2 2
2 4
3 3
1 2
1 2
3 4
4 5
5 5
1 3
1 2
3 5
1 3
2 5
2 4
4 5
1 4
5 5
3 5
4 5
2 3
1 3
1 4
1 2
2 4
2 2
2 3
5 5
4 4
1 2
1 4
3 4
1 1
4 4
2 5
1 3
5 5
3 3
3 3
1 3
1 5
3 5
2 4
4 5
1 4
1 4
2 5
2 5
3 5
1 5
3 4
3 4
3 5
2 4
2 4
1 5
3 5
4 5
4 4
1 3
1 1
1 2
1 3
4 5
2 3
5 5
1 2
1 2
2 4
3 5
4 5
1 4
1 3
1 3
2 5
4 5
1 5
5 5
2 3
1 3
4 4
4 5
1 3
1 2
2 5
3 4
1 4
1 4
1 5
4 5
2 4
3 4
3 4
3 3
2 5
1 2
2 4
3 5
2 4
3 3
1 2
2 2
2 5
3 5
1 2
2 3
1 5
4 4
2 2
2 3
4 5
2 5
1 5
2 4
3 5
3 4
4 5
2 4
1 2
5 5
2 5
1 2
5 5
3 5
4 5
4 5
1 3
3 3
5 5
2 2
2 3
4 5
1 5
4 4
2 3
2 5
3 5
2 2
2 4
1 1
1 5
1 2
2 5
3 4
1 2
1 3
4 5
1 3
1 2
1 3
2 3
1 5
2 3
1 3
2 4
3 4
1 1
4 5
4 5
2 5
1 2
3 4
2 3
1 5
3 5
2 2
1 3
1 5
4 5
4 4
2 5
5 5
4 4
5 5
4 5
4 4
4 4
2 3
2 5
2 4
2 5
3 5
3 5
3 5
1 5
4 5
2 3
1 3
2 2
2 3
1 2
3 4
2 3
2 4
1 4
5 5
2 5
1 1
2 5
5 5
1 2
2 2
1 4
3 3
3 4
4 5
1 4
1 2
1 4
1 2
3 3
1 5
2 4
2 4
1 2
1 2
2 5
3 4
1 5
3 4
3 4
1 2
2 4
3 5
5 5
5 5
1 2
1 4
2 4
2 3
1 1
4 5
3 5
3 5
1 5
2 5
2 5
3 4
2 5
2 2
2 5
1 3
2 2
3 5
3 4
5 5
1 3
2 5
3 4
1 5
4 5
2 4
1 3
3 3
1 5
2 2
5 5
2 2
3 5
1 1
1 4
2 5
1 4
2 5
3 4
1 3
1 1
2 5
1 4
2 3
2 5
1 1
3 5
4 5
1 1
3 4
2 4
3 5
2 4
1 3
2 2
1 1
3 5
4 4
2 3
4 4
2 5
4 4
2 4
2 5
2 5
3 3
4 4
3 5
5 5
3 5
4 5
3 3
2 3
3 5
3 5
4 5
1 3
1 4
1 1
2 5
3 3
4 4
1 3
1 2
2 3
2 4
2 4
3 4
3 3
3 3
2 3
5 5
4 4
4 4
1 5
1 4
1 2
2 5
2 3
4 5
3 5
1 2
2 5
1 4
1 2
2 4
2 5
5 5
1 2
1 3
4 4
2 2
2 3
4 4
1 5
2 3
1 2
1 4
2 4
1 3
5 5
1 5
2 3
1 4
1 3
3 4
3 4
1 3
1 2
4 4
4 4
3 3
1 2
1 3
4 4
4 5
1 2
4 5
3 5
3 3
1 5
1 3
1 1
3 4
1 4
3 4
2 3
3 3
2 5
1 4
3 4
1 2
2 3
1 5
2 3
1 2
2 3
2 5
3 4
2 3
1 3
4 5
2 2
1 5
2 5
2 2
5 5
4 5
3 3
1 5
2 4
3 4
3 5
3 4
1 3
1 3
1 1
3 4
1 2
1 2
2 4
1 3
2 2
2 4
3 5
2 4
2 5
2 4
1 5
5 5
2 4
1 4
3 3
1 4
2 5
1 4
1 2
1 3
1 5
3 4
3 4
5 5
2 3
1 5
4 4
1 2
1 5
2 3
3 4
2 5
1 5
3 4
1 5
2 2
1 2
4 5
1 3
3 4
2 4
2 3
2 5
1 3
2 3
3 5
2 3
4 5
3 4
2 2
2 3
1 5
1 2
1 3
1 3
4 4
1 4
2 3
2 3
1 2
4 5
2 3
2 3
2 5
1 2
4 5
3 4
2 4
2 5
2 4
3 5
1 4
2 4
1 2
1 3
1 4
2 5
1 4
2 2
2 3
1 4
3 4
4 5
1 4
3 4
1 4
3 4
1 3
3 3
4 4
3 4
4 4
1 1
3 5
3 4
1 5
1 5
4 4
2 2
1 3
1 5
1 4
1 2
2 5
2 3
3 5
1 3
3 3
3 3
4 5
1 5
4 5
2 5
3 5
3 4
2 4
1 2
1 4
1 5
2 4
1 4
3 4
3 3
1 3
1 1
3 5
1 3
2 3
3 4
1 3
2 4
2 5
2 5
5 5
2 3
5 5
2 4
3 3
3 3
2 4
2 3
3 3
1 1
1 4
3 4
1 3
1 1
1 2
4 4
2 5
2 5
1 3
2 4
4 5
4 5
1 5
3 4
5 5
1 3
3 5
3 5
1 4
1 5
4 4
1 5
1 2
1 4
1 4
1 5
2 5
4 5
1 5
1 5
1 3
1 5
2 4
2 5
3 3
4 5
2 4
2 5
2 3
1 4
3 3
3 4
1 4
2 3
2 5
1 5
2 3
3 5
1 1
5 5
1 5
1 2
1 5
1 4
3 5
3 3
5 5
2 5
3 4
1 4
3 4
1 1
2 4
2 4
3 5
1 4
2 5
4 5
4 4
1 3
3 4
3 5
2 5
2 4
2 3
5 5
1 2
1 1
3 5
2 3
3 5
1 4
2 3
2 2
2 5
3 4
2 5
2 4
1 2
1 2
2 3
3 5
1 4
2 5
4 5
2 5
4 5
1 4
1 1
3 3
1 5
1 2
5 5
4 4
1 1
2 5
2 4
4 4
3 3
1 5
1 4
1 2
4 5
3 5
2 3
1 3
4 5
4 5
4 4
2 3
3 5
4 5
3 5
2 3
1 4
2 3
1 4
3 5
2 3
4 5
5 5
1 3
3 4
4 5
4 5
2 4
1 3
5 5
2 5
1 2
4 4
3 5
2 5
2 2
1 4
1 5
2 4
2 5
2 5
2 2
1 4
1 3
4 5
1 5
3 5
2 3
1 2
5 5
2 2
1 1
1 4
1 2
3 4
3 3
5 5
2 4
2 4
4 4
5 5
3 3
3 4
1 3
1 3
1 4
2 3
2 3
2 3
2 5
2 3
2 5
4 5
3 3
5 5
1 3
1 2
1 5
4 5
4 4
2 5
1 1
1 5
3 4
1 2
3 4
5 5
2 4
3 4
1 2
3 4
2 3
3 4
1 4
3 4
1 3
1 4
5 5
1 5
3 4
1 3
4 5
4 5
1 4
2 2
1 5
1 4
2 3
2 5
2 3
5 5
1 5
2 3
1 4
3 5
3 4
1 5
1 5
1 4
2 3
4 4
1 4
1 4
1 3
3 5
1 5
3 4
3 5
4 5
1 3
1 2
4 5
4 5
3 5
3 4
1 1
3 5
3 4
5 5
1 4
4 5
4 4
3 5
2 5
1 3
1 5
3 4
2 4
3 4
3 4
1 5
1 3
2 5
1 2
3 4
2 5
2 3
1 5
5 5
4 4
4 4
3 4
1 5
1 4
1 1
1 3
1 3
1 5
2 5
1 2
1 3
1 5
3 4
4 5
3 5
1 2
1 5
1 4
2 4
2 5
1 4
1 4
4 5
4 5
1 1
1 5
4 4
4 5
3 5
1 5
1 3
2 2
1 3
1 3
2 4
2 3
3 3
2 4
2 4
4 4
3 5
2 3
2 3
1 5
1 2
2 3
2 4
4 4
2 3
3 5
1 1
2 2
2 4
2 5
1 2
4 5
2 4
5 5
1 5
2 3
3 5
3 3
3 3
1 3
2 4
2 3
2 4
1 5
1 4
2 5
3 4
5 5
3 5
1 4
2 5
2 4
4 5
2 4
2 2
1 3
1 1
3 5
3 5
3 5
1 1
1 3
2 5
3 5
1 2
1 4
1 1
2 3
2 5
1 2
3 4
1 1
1 2
2 2
1 3
1 4
1 3
1 2
5 5
3 4
1 3
2 5
3 5
2 4
1 3
1 3
1 3
1 5
2 3
3 5
2 4
3 4
1 1
1 2
2 4
2 3
2 4
1 5
3 5
3 3
2 4
1 1
2 5
1 4
1 2
1 3
2 4
3 4
3 5
2 3
5 5
2 5
1 5
3 4
2 2
3 5
1 4
3 4
2 4
1 4
3 4
2 4
1 3
1 2
2 4
5 5
2 3
2 4
3 4
4 5
3 4
2 4
2 4
2 4
4 4
2 5
4 4
1 4
3 5
1 3
2 4
4 4
3 3
2 3
4 4
5 5
1 2
2 4
3 3
1 3
2 3
1 3
1 4
3 5
1 5
1 1
5 5
5 5
1 3
1 4
3 4
3 5
4 5
4 5
3 4
3 5
1 4
5 5
1 4
1 3
1 5
2 5
2 5
3 4
1 3
2 3
1 2
2 2
1 3
2 4
2 3
1 4
3 5
3 5
2 3
1 2
3 4
1 4
2 4
4 5
2 5
4 4
1 3
2 3
3 4
1 1
3 4
2 2
1 2
3 3
2 2
3 4
1 3
1 4
2 3
2 2
4 5
4 4
3 3
1 3
2 2
4 5
1 2
3 3
1 4
1 5
4 5
1 5
3 3
2 4
2 3
1 5
1 5
2 4
1 4
1 2
1 5
3 3
2 3
2 3
3 3
5 5
1 5
1 2
4 4
1 5
5 5
2 3
3 4
1 5
3 3
1 2
2 5
3 5
4 4
4 4
3 4
1 2
5 5
1 5
1 1
1 5
1 4
2 3
1 3
1 4
1 2
3 5
1 2
1 1
4 5
4 5
1 1
5 5
3 3
2 2
1 5
1 4
1 5
2 3
1 3
2 2
3 4
1 1
2 2
3 5
5 5
2 4
2 5
1 3
3 3
4 5
1 5
2 2
3 4
4 4
4 5
2 2
4 5
1 4
1 5
2 5
4 4
1 4
1 4
4 5
3 4
1 1
4 5
1 1
3 4
2 4
3 4
2 4
3 5
1 3
2 4
4 4
3 4
4 5
2 3
2 4
2 4
2 4
1 5
1 4
3 5
1 2
1 5
1 5
4 4
3 4
4 5
1 4
2 4
3 4
2 4
3 4
3 5
1 5
3 3
3 5
2 3
1 2
1 1
2 5
2 3
4 4
2 5
1 4
1 3
4 5
1 3
3 3
4 5
1 5
1 2
5 5
5 5
1 3
4 4
4 5
4 5
2 2
1 4
2 2
2 3
4 5
5 5
3 4
3 4
1 1
3 5
3 4
3 3
3 3
1 1
2 5
2 2
1 1
1 3
3 3
3 5
3 5
2 5
2 3
2 5
1 3
4 5
3 4
2 3
2 4
1 3
2 5
2 4
2 4
1 3
3 3
3 5
3 5
1 3
4 5
3 4
2 4
1 5
1 1
2 5
1 1
1 5
2 2
3 4
1 5
2 3
3 5
3 4
4 5
3 5
1 2
1 5
3 4
1 4
1 5
4 5
1 1
2 2
2 3
2 4
1 3
1 4
2 3
4 5
4 4
1 2
4 4
3 5
1 4
1 4
2 5
1 1
1 3
1 3
2 4
1 3
4 5
3 4
4 5
2 4
4 5
2 5
3 5
1 2
2 3
2 5
2 4
4 5
3 3
4 4
2 3
2 5
2 4
1 4
1 4
3 3
1 5
1 5
3 4
3 3
4 4
2 3
1 4
1 3
1 2
2 3
1 1
1 5
2 5
1 5
2 2
3 5
1 4
2 2
1 3
3 4
2 4
1 2
1 2
1 4
3 4
1 3
1 2
3 3
4 4
2 5
4 4
3 5
3 5
1 5
3 4
1 5
2 3
1 2
2 4
1 3
2 3
4 5
3 3
2 3
1 1
1 1
2 4
3 4
1 3
1 3
3 3
1 3
5 5
1 3
2 3
1 5
1 2
2 5
1 3
3 4
2 5
3 5
4 5
5 5
2 4
1 4
2 5
2 3
3 4
1 2
2 5
3 4
1 5
1 2
1 4
4 5
2 4
2 4
1 3
1 5
2 3
4 5
2 5
1 5
3 4
1 1
4 5
4 4
2 3
2 3
2 4
2 3
1 1
1 2
4 5
2 2
1 2
1 4
2 4
1 2
2 5
3 3
2 3
4 5
4 5
1 3
1 2
1 3
2 4
2 5
2 4
1 2
1 1
1 2
4 4
5 5
3 5
1 3
3 5
3 5
5 5
1 4
1 1
3 4
1 4
2 5
2 2
2 4
2 3
1 3
2 3
3 5
2 5
1 3
1 3
2 5
2 5
1 2
4 5
1 3
3 4
2 3
1 5
3 3
1 3
1 3
4 5
3 5
1 5
3 4
1 2
2 5
4 5
2 3
1 2
5 5
3 5
2 5
4 5
1 3
1 2
3 5
3 3
1 5
4 5
3 4
1 3
2 4
4 5
3 4
5 5
1 3
2 2
2 2
2 3
1 3
4 5
4 4
2 4
5 5
1 2
1 3
5 5
2 4
1 1
3 4
3 5
1 3
3 5
2 5
1 3
3 4
2 3
1 4
4 5
2 4
1 2
1 1
2 5
3 4
3 4
2 4
4 5
1 4
3 4
4 4
1 5
2 4
4 4
1 5
4 5
4 5
1 2
2 2
1 5
1 3
1 5
1 5
1 1
1 4
1 3
1 5
4 4
2 4
4 5
2 5
5 5
2 5
2 4
3 4
3 3
5 5
2 4
1 3
1 3
1 2
1 2
1 4
1 3
2 4
1 2
3 5
4 5
3 5
1 5
4 5
1 4
1 4
2 3
4 5
3 5
1 4
1 5
2 4
3 5
1 3
1 2
1 2
3 5
1 3
4 4
2 4
2 2
2 5
3 3
5 5
5 5
2 5
2 3
2 3
1 4
3 5
4 4
2 5
1 4
4 4
1 3
4 4
5 5
5 5
4 5
2 5
3 5
2 5
2 3
1 2
3 4
1 2
1 3
2 3
2 3
3 4
5 5
3 3
5 5
3 5
3 4
2 4
3 5
3 5
3 4
3 3
1 5
1 4
1 2
4 5
1 3
5 5
2 4
2 3
1 1
3 4
4 5
2 3
1 4
2 3
3 5
3 4
3 3
1 5
1 2
1 1
1 2
4 4
1 3
1 5
1 5
1 3
3 3
1 4
1 2
3 5
1 2
1 1
1 4
2 3
4 5
4 5
3 5
1 5
4 5
2 5
5 5
2 4
1 2
1 4
2 4
1 3
1 2
2 2
3 3
4 5
2 5
1 4
4 5
2 5
2 2
1 4
1 3
2 4
1 1
2 5
1 3
1 4
3 4
3 4
1 3
2 4
2 3
2 3
5 5
1 3
2 3
2 5
2 4
2 5
2 3
1 2
1 1
1 5
2 4
4 5
3 4
5 5
1 2
3 5
3 5
2 5
2 5
2 3
4 4
3 5
4 5
2 4
1 3
4 5
1 1
1 4
1 4
2 2
2 5
1 2
3 4
2 2
2 4
1 4
1 5
3 3
1 2
3 4
1 5
1 4
2 5
2 4
1 2
1 3
2 5
3 5
4 5
4 5
2 3
3 3
2 4
1 4
4 5
4 5
2 4
2 4
5 5
1 3
3 5
3 5
3 4
4 5
3 5
4 5
2 4
1 3
3 5
5 5
5 5
2 3
2 2
5 5
2 4
4 5
2 2
1 3
4 5
1 3
4 5
2 2
1 2
4 4
1 3
5 5
3 4
1 2
4 5
1 2
1 1
1 1
1 3
1 5
1 2
1 5
1 1
3 4
1 5
2 5
4 5
1 3
1 4
1 4
2 4
1 4
1 5
1 3
2 4
2 5
1 3
4 5
1 2
4 4
1 3
1 2
4 5
3 4
4 4
4 4
3 5
2 2
2 4
1 4
5 5
3 4
1 4
3 5
3 4
1 4
1 2
3 4
1 5
3 4
2 5
2 3
1 4
1 5
2 2
3 5
4 5
2 5
3 5
1 2
3 4
2 3
2 4
4 5
1 2
4 5
2 3
3 3
3 5
1 2
1 5
5 5
3 5
2 4
1 3
1 1
5 5
1 5
1 5
4 5
2 5
1 5
1 5
3 3
4 4
5 5
1 3
3 5
2 5
1 5
2 3
3 5
1 5
2 3
5 5
4 5
1 3
1 5
2 3
2 3
1 5
2 4
3 4
3 5
2 5
4 4
1 3
2 2
2 4
1 3
1 5
1 4
4 5
3 4
3 5
3 4
1 5
2 5
1 5
3 5
1 2
3 3
2 4
4 4
1 4
3 5
1 5
3 4
2 5
4 5
2 5
4 5
2 5
1 5
3 5
3 4
1 2
1 3
1 5
4 5
1 4
4 4
3 3
2 3
1 4
1 2
3 3
3 3
1 3
5 5
3 3
2 3
4 5
3 5
3 3
4 5
5 5
3 4
2 2
2 3
1 4
1 4
1 1
4 4
1 3
3 4
4 4
3 5
3 4
2 5
2 3
2 3
3 4
3 3
4 4
2 4
3 4
1 4
1 2
1 3
3 4
1 2
2 3
2 4
2 3
1 3
1 3
2 3
2 4
2 4
1 5
1 5
4 4
1 2
3 3
3 4
4 4
4 4
5 5
3 4
2 5
1 1
1 5
1 2
2 5
2 5
2 3
1 2
1 3
1 4
1 3
4 5
4 5
2 3
4 5
1 2
2 5
3 5
2 4
4 4
1 5
3 4
1 4
1 4
1 2
1 4
2 5
1 5
4 5
3 4
3 3
1 2
1 1
1 1
4 5
2 5
2 4
3 3
1 2
1 5
4 5
1 3
2 4
2 4
3 3
2 3
2 4
3 4
3 3
1 5
2 3
3 3
3 3
1 4
2 2
4 4
2 3
3 4
4 5
4 5
5 5
1 2
2 3
1 2
4 5
1 4
2 3
3 3
3 3
2 4
2 4
2 5
4 5
3 4
1 4
4 5
2 3
3 4
2 3
3 4
2 3
1 2
2 5
3 5
2 4
2 3
4 5
1 4
1 4
1 1
3 4
1 3
3 4
4 5
1 3
2 3
2 3
3 3
5 5
2 5
1 4
1 1
4 5
1 5
4 4
2 3
3 5
4 5
5 5
4 5
1 4
1 2
1 3
2 3
2 3
3 5
1 3
3 4
3 3
3 5
1 2
1 4
1 5
2 4
2 3
1 4
3 4
3 4
4 5
4 5
2 5
3 4
1 3
3 5
2 2
5 5
4 4
5 5
2 4
1 5
4 5
1 4
3 5
2 5
4 4
3 4
1 2
2 3
2 2
1 1
1 2
1 3
3 4
2 4
1 3
2 4
3 5
2 4
4 5
4 5
2 3
4 5
4 4
4 5
2 5
1 2
3 5
4 5
2 3
1 1
2 4
1 3
4 5
1 2
2 4
2 2
3 3
2 3
1 5
1 4
3 4
5 5
1 4
2 2
1 2
1 4
1 2
1 1
2 5
2 4
1 5
3 3
1 4
2 5
4 5
1 5
2 2
4 4
2 3
1 2
4 4
2 2
3 4
1 2
2 5
1 3
1 4
4 4
2 3
1 1
4 5
5 5
4 5
1 5
2 3
2 2
2 2
1 4
2 2
3 5
3 4
3 3
1 3
3 3
1 3
3 4
2 3
2 3
2 3
1 5
2 4
2 3
2 4
3 4
1 2
1 5
1 3
4 5
2 5
3 3
2 3
1 1
1 4
1 5
2 3
1 3
1 4
3 5
1 3
3 4
1 2
3 5
1 4
3 5
1 4
3 4
4 4
1 4
3 5
2 2
3 4
2 4
4 5
1 2
2 5
3 5
1 3
1 1
1 3
1 4
4 5
2 5
2 5
2 5
4 5
2 2
3 5
1 3
1 5
1 5
3 4
3 4
1 5
3 5
4 5
2 2
4 5
2 2
2 5
4 5
1 3
3 3
1 2
1 3
1 1
3 4
2 3
3 4
1 2
1 5
4 5
3 4
1 4
1 5
3 4
2 3
4 5
4 4
3 4
2 5
1 5
4 5
3 4
3 5
2 4
4 5
2 5
5 5
1 4
2 3
1 5
4 5
5 5
3 5
2 3
1 2
2 3
2 4
1 3
3 5
1 2
4 5
3 4
2 2
1 1
2 5
1 4
4 5
2 3
1 5
2 5
4 5
2 4
2 5
1 3
2 4
1 4
2 2
2 5
1 5
4 5
1 4
5 5
3 5
1 3
2 3
2 3
1 3
3 5
1 3
1 5
2 3
4 5
4 4
2 5
1 4
1 5
5 5
1 1
3 5
1 2
2 3
3 5
4 5
1 4
1 5
2 4
2 4
5 5
1 5
1 4
1 2
2 4
2 2
3 5
1 2
2 4
1 1
4 4
1 3
2 5
3 4
2 3
4 5
3 5
2 5
1 4
3 3
3 4
3 3
1 3
3 5
2 3
2 3
1 2
1 1
1 3
3 3
1 2
1 2
1 5
1 4
2 3
1 4
4 5
3 3
3 4
2 5
2 3
2 3
1 3
5 5
2 3
1 5
2 2
3 5
2 5
2 3
2 4
5 5
1 4
1 3
1 3
3 5
2 3
3 5
4 5
4 4
3 5
2 4
3 4
2 4
2 5
1 3
1 2
2 4
2 4
1 5
4 5
3 4
3 5
1 2
4 5
2 5
3 3
4 5
4 4
2 4
2 4
2 3
5 5
2 5
1 3
1 3
2 4
1 1
1 2
3 3
5 5
4 5
4 5
1 3
2 2
2 3
3 3
5 5
3 5
1 3
2 5
1 3
1 3
2 3
2 5
3 3
1 2
4 4
1 4
4 5
4 4
4 5
2 3
3 5
1 4
1 4
4 5
5 5
4 5
2 2
2 5
3 4
3 5
2 2
2 2
1 2
3 5
1 2
3 5
2 4
3 5
3 3
1 2
3 4
3 3
2 4
4 4
4 5
3 4
1 5
3 5
5 5
3 4
4 5
4 5
1 3
3 4
3 5
3 4
2 2
4 5
3 4
1 3
2 3
4 5
4 5
1 4
4 5
3 4
4 5
3 5
1 1
4 5
1 5
1 5
1 5
1 5
2 3
1 3
2 3
3 5
2 4
2 3
1 3
2 2
5 5
1 4
2 4
1 5
3 4
2 5
1 5
5 5
1 3
2 4
1 3
1 3
2 2
4 5
1 1
1 1
2 5
3 5
2 3
3 4
4 5
1 1
2 4
2 3
1 1
1 2
2 4
1 3
4 4
3 4
3 5
4 4
2 5
2 5
2 4
2 5
3 3
1 3
1 3
2 4
3 4
1 5
3 5
4 5
2 3
3 5
4 5
1 5
2 5
1 4
2 3
3 5
1 3
5 5
3 5
2 5
2 3
3 4
2 4
3 4
1 2
3 5
1 5
1 2
2 5
4 4
3 5
3 5
1 2
1 3
3 5
3 3
3 4
3 4
2 5
1 1
1 3
3 5
2 3
1 5
2 4
2 5
2 5
4 5
2 3
2 5
2 2
3 3
2 5
2 2
1 5
2 2
3 3
4 5
3 5
3 4
1 4
1 3
1 4
4 5
1 3
3 4
2 5
2 5
4 4
4 4
2 3
4 4
1 3
3 3
1 3
3 5
1 3
3 3
3 4
5 5
1 5
5 5
3 5
2 5
1 5
3 5
1 1
1 4
2 4
3 5
5 5
1 2
2 3
3 4
1 2
3 4
3 5
4 5
4 5
3 5
1 3
2 4
2 4
2 2
4 4
2 5
2 3
3 4
4 5
2 5
3 5
1 1
1 4
2 3
1 1
3 5
1 2
1 4
3 5
1 4
2 3
1 5
1 4
4 4
1 3
2 4
1 2
1 5
3 5
1 4
1 1
2 5
1 1
3 4
1 2
1 5
3 4
2 3
4 5
2 5
1 5
1 1
2 3
4 5
1 2
1 1
1 1
1 5
1 5
2 2
2 3
2 5
2 4
1 5
1 3
4 5
3 3
2 5
1 3
2 4
1 3
1 2
2 3
2 3
2 4
3 4
2 4
1 3
4 5
3 5
2 4
2 2
1 1
5 5
1 5
1 5
3 4
2 5
1 5
2 3
1 1
2 3
4 5
1 3
2 3
2 4
2 4
2 3
1 4
4 5
2 3
1 1
1 2
1 2
1 1
1 3
1 5
2 3
4 4
3 5
3 4
3 4
3 3
1 1
3 4
2 4
3 4
4 5
1 1
1 4
1 1
2 3
3 4
3 3
2 3
1 3
2 3
3 5
1 2
4 4
4 4
4 5
3 5
4 5
1 2
1 3
4 5
3 5
1 2
2 3
5 5
1 3
3 5
5 5
2 4
1 5
1 2
1 5
2 3
3 3
4 5
2 2
1 5
4 5
1 2
2 4
1 1
4 4
1 4
2 4
2 3
4 5
3 4
4 5
1 2
2 2
5 5
4 5
2 5
3 4
3 4
2 3
2 3
2 4
1 3
1 5
1 3
2 2
1 1
1 4
3 4
1 2
1 4
1 5
1 2
3 4
1 5
3 4
2 3
2 3
2 5
3 5
3 5
1 1
2 4
5 5
2 4
2 3
3 5
2 3
3 5
4 4
3 4
2 5
1 3
3 4
2 3
3 5
1 3
1 4
1 3
1 5
1 3
3 4
3 3
3 3
1 2
1 3
3 3
1 3
1 2
2 3
2 4
1 2
2 3
3 5
3 4
1 2
2 5
1 1
1 3
2 4
3 4
1 4
2 3
1 3
1 4
1 5
1 3
1 2
1 4
2 5
1 2
4 4
1 3
1 3
2 4
1 2
1 5
3 5
2 3
3 5
1 5
2 4
1 3
2 5
4 4
1 5
2 3
4 5
4 5
1 5
1 3
2 2
2 4
3 5
1 5
4 5
4 4
3 3
2 5
3 5
1 1
3 5
4 4
3 5
2 5
2 3
1 5
3 3
2 2
3 3
1 5
3 3
1 4
1 2
3 3
3 3
2 4
1 3
3 3
2 3
3 4
3 4
1 2
1 4
1 4
2 3
3 5
1 4
1 4
2 5
1 2
4 5
2 2
4 4
2 4
1 5
1 3
1 1
1 1
1 1
2 4
4 5
3 4
1 5
4 5
1 2
4 4
2 5
1 3
3 4
3 5
3 3
4 4
4 5
2 3
2 4
5 5
2 3
1 3
3 4
2 2
1 1
1 3
1 2
2 4
1 2
3 4
3 5
5 5
1 4
1 5
1 3
2 5
4 4
3 5
2 3
2 4
2 2
4 5
3 4
2 2
2 3
1 5
1 3
3 4
2 3
1 5
1 3
2 3
2 4
1 4
3 4
3 4
2 2
4 5
1 4
3 4
2 5
3 4
3 3
2 3
2 3
2 4
3 5
4 5
1 1
2 5
3 4
4 5
4 4
2 3
1 2
4 5
1 5
3 4
4 5
3 4
2 4
5 5
1 4
2 4
3 5
2 3
3 3
5 5
4 5
1 5
2 4
3 3
3 3
3 4
2 4
1 4
2 3
2 2
3 3
1 2
1 4
2 3
3 4
2 4
1 3
1 4
1 4
1 3
1 4
2 3
2 5
2 3
1 3
3 4
3 4
5 5
4 5
1 4
1 3
1 4
2 3
2 3
1 3
2 5
2 5
2 5
3 3
5 5
3 3
4 5
3 4
2 2
1 3
2 4
1 3
1 2
3 5
1 3
3 4
2 2
1 5
2 2
2 3
2 5
1 4
2 2
1 3
5 5
2 5
3 5
4 5
1 2
2 5
2 5
1 3
1 2
2 5
3 4
2 3
1 5
2 5
1 2
3 4
3 3
2 5
1 1
2 4
2 4
2 4
1 3
2 5
5 5
2 3
1 3
4 5
1 3
3 5
2 5
1 4
1 3
2 4
3 4
1 2
1 2
3 5
1 1
4 5
1 3
2 5
2 5
5 5
1 3
5 5
1 4
1 2
4 5
1 3
1 5
2 3
5 5
4 5
5 5
2 3
3 5
3 4
2 4
4 5
1 3
1 2
4 5
1 2
3 5
1 5
2 3
1 4
2 3
2 2
2 5
2 3
3 3
2 5
3 5
1 4
1 2
4 4
1 5
2 4
1 3
1 2
4 4
1 3
4 5
2 2
4 5
3 4
4 4
2 5
1 4
1 3
2 3
3 4
4 5
4 5
3 4
1 4
1 5
1 4
1 2
3 4
2 5
4 5
2 4
3 4
1 2
3 5
2 4
2 3
1 4
5 5
3 4
2 3
1 4
2 4
2 4
1 1
2 4
2 5
2 3
4 4
5 5
1 3
1 3
2 2
4 5
1 1
2 4
2 3
4 4
2 4
4 5
4 5
1 5
1 3
2 3
2 5
3 5
4 4
3 5
3 5
3 4
3 5
3 4
1 5
1 5
2 3
4 5
1 4
1 4
1 1
2 3
1 4
1 2
1 4
2 3
3 4
4 5
1 3
1 2
1 3
1 3
1 5
2 5
4 5
4 5
4 5
1 1
1 3
2 2
3 5
2 5
1 3
2 3
4 5
2 2
3 5
2 2
1 4
1 2
2 5
1 2
4 5
1 2
1 3
2 2
2 5
2 4
2 5
4 5
1 1
1 5
2 5
3 5
2 2
4 5
1 5
1 3
4 4
4 5
1 5
3 5
1 2
2 4
3 5
4 5
1 5
1 1
2 4
3 4
1 3
1 4
3 4
4 5
1 1
4 5
4 5
3 4
1 5
3 3
1 4
3 4
3 4
2 3
3 5
2 4
1 1
1 5
2 3
3 4
1 4
1 1
1 1
1 4
1 1
3 5
4 4
1 4
2 4
1 2
3 5
3 4
4 5
3 4
4 5
5 5
2 2
3 4
2 5
3 5
2 5
4 4
1 3
4 5
1 5
2 5
4 5
3 4
1 4
1 2
2 4
2 3
1 5
1 4
1 4
2 4
2 4
3 3
2 5
3 5
1 4
2 5
5 5
3 5
2 3
2 4
2 4
5 5
1 2
4 4
2 5
2 3
2 5
1 4
2 5
4 4
3 5
5 5
1 1
1 5
1 3
2 3
2 5
4 5
2 3
4 4
1 4
1 2
1 3
4 5
2 4
4 5
1 2
2 3
1 4
4 5
1 2
4 5
3 4
1 1
2 3
2 4
2 4
5 5
2 5
1 5
3 4
3 4
3 3
2 3
2 4
5 5
4 5
2 4
1 4
1 4
3 4
1 5
1 3
2 4
1 3
5 5
2 3
4 5
1 5
2 3
1 5
4 5
2 5
1 3
4 5
2 3
3 3
2 3
4 4
4 4
1 2
1 3
2 5
1 4
1 4
1 1
1 2
4 5
2 3
4 5
1 3
4 4
1 4
3 5
2 5
1 2
1 3
2 4
1 1
3 5
1 5
2 5
3 5
2 4
3 3
2 4
2 4
3 5
1 1
1 5
1 4
1 5
5 5
2 3
2 5
1 3
1 5
4 5
1 2
1 5
1 1
1 2
2 4
2 4
2 5
2 5
3 4
5 5
4 4
1 3
4 5
3 4
4 5
1 4
4 4
1 2
3 4
2 3
2 5
3 4
1 3
3 4
3 3
2 4
2 3
3 4
2 3
3 5
2 5
2 3
2 5
5 5
4 4
2 3
2 5
1 2
2 5
2 4
2 2
2 4
3 4
2 4
4 5
1 4
2 2
4 5
1 4
1 3
2 3
1 3
2 3
4 5
1 2
1 4
4 4
4 5
2 3
2 5
3 4
1 1
3 3
2 3
5 5
3 4
5 5
1 5
3 3
2 4
1 2
1 4
1 5
3 5
1 2
1 5
2 3
3 4
1 2
1 4
1 5
1 5
3 4
4 5
4 4
3 5
2 5
1 2
1 5
1 1
2 2
1 4
1 2
1 5
3 5
2 2
2 4
3 5
1 5
1 5
5 5
4 5
1 3
2 3
3 4
2 2
2 4
1 3
1 5
2 5
2 4
2 5
1 2
1 3
2 3
1 1
1 5
1 2
1 5
5 5
1 2
3 4
3 5
5 5
1 2
1 1
5 5
5 5
1 4
2 4
3 5
1 3
1 2
2 2
2 3
1 5
1 2
1 2
1 4
1 3
1 4
2 5
1 2
4 5
3 3
3 3
4 4
2 4
1 3
1 3
2 2
4 4
1 3
4 4
2 4
3 4
2 3
1 3
3 5
1 4
3 5
3 4
4 5
1 2
2 3
2 5
2 5
3 4
1 5
1 4
1 3
4 4
1 1
2 3
3 4
1 5
3 5
2 3
2 5
1 2
5 5
1 4
2 4
1 2
3 5
1 5
1 5
2 2
1 3
1 3
2 5
1 4
1 4
3 5
1 5
2 4
1 5
1 3
1 3
4 5
1 5
1 3
3 5
3 5
2 3
1 4
3 5
3 4
2 2
5 5
1 5
3 3
1 2
3 3
4 5
1 2
4 5
1 5
5 5
1 4
1 5
2 2
2 5
3 5
4 4
3 5
3 4
1 5
2 3
2 5
1 3
1 5
1 3
3 5
1 5
3 5
1 1
1 5
2 3
1 4
2 4
5 5
1 4
1 1
2 2
1 3
3 5
5 5
1 1
1 5
1 2
2 3
1 1
1 1
1 4
2 3
1 5
1 4
2 5
1 1
1 1
2 4
3 5
1 3
2 5
1 4
2 2
2 4
1 1
1 3
2 3
4 5
2 5
4 5
5 5
1 5
3 5
2 4
3 4
2 4
2 5
1 5
4 5
2 5
4 5
3 3
1 5
4 5
1 2
1 1
4 4
3 4
4 5
4 5
3 3
1 4
1 2
1 2
1 1
2 5
1 4
1 2
2 3
3 3
1 1
4 4
3 5
1 5
3 4
4 5
1 5
3 3
1 2
1 1
4 5
2 5
1 4
1 5
1 4
4 5
1 2
1 4
5 5
2 2
1 3
1 4
2 4
1 2
1 5
3 4
1 3
5 5
1 4
1 1
3 3
2 4
3 4
2 5
2 3
1 3
1 4
3 5
1 5
3 4
1 5
1 1
2 5
5 5
2 4
3 4
1 1
2 4
1 5
1 3
4 4
3 5
3 3
2 2
1 1
2 5
1 5
4 4
2 3
2 2
1 5
1 4
1 3
2 4
3 3
1 4
2 3
3 5
2 2
1 2
2 4
4 5
1 3
2 5
3 4
1 2
2 3
5 5
4 4
3 3
1 4
2 3
2 3
2 3
3 5
1 4
4 4
3 5
4 4
2 3
4 5
4 4
1 3
2 5
1 4
2 4
2 3
2 4
1 2
2 5
4 5
2 3
1 2
3 4
1 4
4 5
3 5
1 4
3 3
4 5
4 4
3 5
2 3
2 3
1 4
5 5
3 4
1 1
3 3
3 5
4 5
3 5
3 4
4 5
2 4
3 5
1 5
1 3
3 4
3 5
4 5
1 3
2 4
3 5
3 5
1 5
1 2
4 5
2 4
2 4
3 4
1 1
1 3
3 4
1 3
3 5
3 5
4 5
3 5
3 3
2 2
4 4
2 5
3 4
3 4
4 5
1 3
4 5
2 3
1 4
1 2
1 3
1 1
1 2
3 3
4 5
1 2
1 2
1 4
2 5
3 5
4 5
2 5
2 2
2 3
1 4
1 4
5 5
3 4
3 3
2 3
4 5
1 1
2 5
1 4
1 2
1 5
3 5
1 5
1 1
1 3
3 3
4 4
2 3
2 5
2 4
1 4
2 5
5 5
1 2
3 5
2 5
3 3
2 5
3 3
2 3
3 4
3 5
1 4
2 4
3 5
5 5
1 3
4 5
1 5
5 5
2 4
4 4
3 5
1 3
3 3
5 5
1 4
3 5
1 2
2 3
1 2
4 5
3 3
1 3
3 4
2 4
2 3
4 5
3 5
1 4
2 5
1 2
1 4
3 5
2 4
2 5
1 3
2 3
3 5
1 3
5 5
3 4
1 5
3 3
2 3
2 2
1 1
2 5
2 4
2 4
1 2
2 4
4 4
5 5
2 3
2 2
5 5
1 2
2 2
5 5
3 4
1 5
3 4
4 5
2 4
2 2
1 2
3 4
2 3
4 5
1 2
2 5
1 1
2 5
1 1
1 5
3 5
1 5
1 5
3 4
2 5
1 1
3 4
2 4
3 5
1 5
2 2
3 5
4 5
3 5
1 2
1 4
1 4
3 3
4 4
2 3
4 5
1 3
1 2
1 3
2 2
2 4
3 3
2 4
1 4
2 3
1 3
2 5
1 3
4 5
1 4
2 4
3 4
1 3
3 4
2 5
1 4
2 3
2 4
2 4
1 5
4 4
2 5
1 3
1 3
3 5
4 4
1 1
4 5
1 4
4 5
2 4
4 5
2 5
4 5
2 5
1 1
3 3
1 2
4 4
1 3
4 4
1 2
3 4
4 5
1 4
1 5
2 5
3 4
1 3
2 5
5 5
1 2
1 5
5 5
1 3
3 4
1 4
4 5
2 5
3 3
1 5
1 4
3 3
3 5
1 1
2 3
2 5
2 5
3 3
3 5
2 2
1 5
2 5
1 2
1 4
1 3
3 5
1 4
1 5
3 4
3 4
1 1
2 3
1 4
2 5
3 3
3 3
2 5
2 3
5 5
3 5
2 4
4 4
1 2
3 5
1 2
1 3
4 4
1 5
1 1
1 2
1 4
1 4
1 4
4 5
3 5
2 3
1 5
3 3
2 3
1 3
2 2
2 3
3 4
2 3
1 4
2 2
5 5
2 5
1 1
4 5
2 4
3 5
5 5
2 3
2 3
3 4
1 5
3 4
3 5
5 5
1 1
1 4
2 4
4 5
1 5
1 1
4 5
3 3
1 4
2 3
4 5
2 5
2 3
3 5
3 5
3 5
3 3
2 3
2 3
2 5
2 4
2 3
2 3
3 3
2 3
3 4
2 4
2 4
1 4
3 4
4 5
2 5
5 5
2 5
2 5
1 4
2 5
2 5
4 5
1 5
2 2
1 5
1 2
2 2
1 4
4 5
4 4
3 3
2 3
4 5
1 3
3 5
4 4
3 5
1 2
1 4
1 3
1 2
1 2
3 4
4 5
1 4
1 4
3 3
3 3
2 4
4 4
2 5
3 3
1 5
3 4
4 5
2 5
3 5
1 4
3 5
1 4
3 5
1 1
1 4
4 4
1 3
2 5
1 5
4 5
3 4
3 3
5 5
1 3
1 5
1 2
2 3
2 3
2 2
4 4
1 2
1 2
4 5
2 4
1 2
1 1
2 5
2 4
1 5
3 5
5 5
1 3
3 4
4 5
3 4
3 4
2 5
3 4
1 2
3 4
1 5
5 5
1 1
2 3
3 4
1 2
1 5
3 5
2 4
2 2
2 3
1 4
3 5
4 5
5 5
2 5
2 3
2 4
1 3
2 5
1 1
4 4
1 1
2 3
2 3
4 5
1 5
1 5
3 3
3 5
2 4
3 3
3 3
1 5
4 4
3 5
1 2
3 3
1 4
3 5
2 4
1 2
2 5
2 4
3 3
1 5
4 5
1 1
2 4
1 4
4 4
1 4
1 5
4 5
2 5
2 2
2 2
3 4
1 4
1 4
3 3
2 5
1 5
3 5
1 5
1 3
3 4
1 1
4 5
3 5
2 5
1 4
4 5
1 3
1 2
3 5
2 5
1 2
5 5
3 5
1 4
2 5
2 4
2 2
2 5
4 5
1 5
1 5
2 2
2 3
3 3
2 5
1 1
2 4
5 5
1 5
4 5
2 2
3 4
2 5
1 4
2 5
3 3
2 4
2 3
2 5
1 3
1 1
2 5
1 4
3 5
4 5
4 5
1 4
2 4
1 4
2 3
3 5
1 4
2 5
1 1
3 3
2 2
1 1
1 5
3 3
2 3
3 3
1 4
2 5
2 2
1 5
1 5
1 4
1 2
2 5
2 4
3 4
4 5
1 5
1 2
1 5
3 5
3 4
2 4
1 2
4 5
2 4
1 4
4 5
1 4
3 4
2 5
1 3
1 5
1 2
1 2
2 4
3 5
3 5
1 3
4 4
1 4
2 3
1 5
1 2
4 5
1 5
5 5
1 3
2 2
2 2
1 5
4 5
1 3
1 2
3 3
2 4
1 4
1 5
3 5
2 5
2 3
3 3
2 2
3 5
4 5
3 4
4 4
2 5
1 4
2 2
1 3
2 4
5 5
3 3
1 4
3 5
2 4
4 5
1 4
1 1
1 2
3 4
4 5
4 5
2 3
3 5
2 4
2 3
3 5
2 4
1 2
1 4
4 5
1 5
3 4
1 5
1 3
1 4
3 3
2 3
2 2
1 2
2 3
4 5
3 5
3 4
3 5
3 5
2 3
2 5
3 5
2 5
1 3
4 5
2 5
3 5
4 5
2 4
2 2
4 5
4 5
2 3
2 3
2 3
1 4
2 4
5 5
2 5
2 4
4 4
2 3
2 3
1 3
3 5
1 3
3 5
1 4
4 5
1 3
1 2
4 5
1 3
2 5
4 5
4 5
2 4
5 5
1 4
1 4
4 5
1 3
2 3
3 3
3 4
1 4
4 4
2 2
1 4
1 2
3 3
1 1
2 2
3 5
4 5
4 5
4 5
4 5
1 2
1 4
3 3
2 3
1 1
2 5
1 2
2 3
4 4
3 3
4 5
2 5
1 4
1 4
5 5
3 3
2 4
4 4
1 3
3 4
5 5
1 3
1 5
2 3
3 5
2 4
2 4
1 5
1 2
1 2
2 5
3 5
3 5
2 3
1 4
3 3
1 1
1 2
2 2
2 5
1 1
1 3
2 5
1 4
1 1
3 5
1 3
1 4
3 3
1 3
4 5
4 4
2 4
2 5
1 1
2 3
4 5
3 3
1 5
2 3
3 5
1 1
1 1
3 4
2 3
2 5
2 2
2 3
1 1
2 2
4 5
2 3
4 5
1 2
1 1
2 2
1 3
4 4
2 4
1 5
3 4
3 5
2 4
2 3
3 4
1 4
1 3
4 4
1 1
3 5
3 5
4 5
1 3
4 4
1 2
3 3
4 5
5 5
3 4
1 2
3 5
1 4
3 3
2 5
1 4
4 5
1 5
2 2
1 3
1 2
4 4
4 5
1 5
2 3
1 3
1 5
1 4
2 4
1 5
1 5
4 5
1 3
2 3
3 4
3 4
2 3
3 3
1 2
1 3
4 5
1 4
1 3
3 3
1 5
1 1
3 4
2 2
1 3
1 5
4 5
1 2
1 1
2 3
4 5
2 3
1 4
2 4
3 4
4 5
2 2
2 4
1 5
3 3
1 1
3 5
2 3
1 3
1 3
2 3
2 5
1 3
3 4
3 3
4 5
2 3
1 5
2 3
4 5
1 4
4 5
4 5
2 3
4 5
3 5
4 5
3 3
4 5
2 4
4 4
1 3
3 4
1 5
3 5
1 4
1 4
1 5
1 3
1 5
4 4
1 4
1 4
4 5
4 4
2 5
4 5
1 3
1 5
1 5
2 3
1 2
1 2
3 3
3 4
4 4
1 1
1 2
3 3
5 5
2 4
2 3
4 5
5 5
2 4
2 5
5 5
2 2
3 4
5 5
1 3
4 5
1 3
2 2
4 5
2 3
4 4
1 5
3 3
2 2
2 4
2 5
2 3
1 5
4 5
2 2
1 2
2 2
2 4
3 4
2 3
4 4
1 3
4 5
4 4
2 2
2 3
4 5
1 5
5 5
2 4
4 5
5 5
1 2
1 2
5 5
3 3
3 4
1 5
2 4
3 5
4 4
2 4
1 1
2 3
2 4
1 2
1 4
4 5
1 3
1 2
3 5
1 2
4 4
2 5
2 5
1 4
2 3
1 5
1 4
1 3
2 4
5 5
2 3
3 4
2 2
2 2
2 4
5 5
3 4
3 4
2 4
3 3
4 5
4 4
2 4
1 5
2 5
4 4
2 3
3 3
3 3
1 5
1 4
1 3
1 2
2 3
1 3
2 3
1 4
1 2
2 3
3 5
3 5
1 1
3 4
1 2
2 5
2 2
3 4
4 5
1 5
3 5
5 5
3 5
3 5
2 5
2 3
3 4
1 5
3 4
2 4
3 4
2 5
2 4
1 1
3 4
3 5
2 4
3 4
3 5
5 5
1 2
1 3
3 4
5 5
2 4
4 5
3 3
4 5
1 4
2 4
4 4
1 5
2 5
1 1
2 3
3 4
1 4
2 3
3 4
2 5
2 2
1 5
1 1
1 2
5 5
4 4
3 3
1 1
2 2
1 3
1 5
2 4
1 2
3 4
2 4
1 5
1 4
3 5
3 5
1 1
1 5
4 5
1 4
3 4
2 5
2 2
4 4
3 5
1 1
5 5
2 4
1 5
2 2
3 4
2 3
1 4
3 5
3 3
1 5
1 4
2 5
5 5
4 5
4 5
2 4
4 4
1 2
1 1
2 2
2 2
2 3
1 5
1 1
1 3
1 2
3 5
4 5
4 5
2 5
3 5
1 2
1 2
3 3
2 5
4 4
1 1
5 5
1 1
2 4
2 3
1 4
2 3
1 4
2 3
2 4
3 3
5 5
1 4
1 2
1 2
2 4
2 3
2 2
3 4
4 5
4 4
4 5
3 4
2 4
5 5
1 5
1 4
4 5
2 4
3 5
4 5
2 2
2 2
4 4
3 4
1 5
3 4
1 3
1 2
1 5
2 4
3 3
1 4
1 3
2 3
3 5
3 4
1 3
2 2
3 5
3 3
1 3
1 5
3 3
2 4
1 5
1 3
1 5
2 5
1 4
2 5
3 5
1 5
1 5
3 4
3 5
3 3
1 3
2 4
2 2
3 4
2 5
1 3
3 5
1 2
2 2
3 4
2 5
2 5
1 5
1 4
3 5
1 2
1 5
4 5
1 3
4 5
1 1
1 5
2 4
1 5
1 3
1 5
3 5
2 3
4 5
4 4
3 5
1 5
4 4
1 5
3 5
3 4
1 1
3 4
4 5
1 2
3 4
1 4
3 3
3 3
2 4
2 3
2 3
1 4
4 5
3 5
5 5
1 4
1 2
3 4
4 5
1 2
2 5
3 3
3 3
4 4
1 2
2 4
1 4
1 1
1 2
3 4
5 5
3 4
1 3
3 5
1 2
1 3
2 4
1 3
1 5
3 5
2 5
2 5
4 4
3 3
3 5
3 5
2 3
2 4
1 4
4 5
4 4
2 5
4 5
3 5
2 5
3 5
2 4
2 4
1 3
1 2
1 4
3 5
3 5
2 4
1 5
4 5
2 5
3 3
3 3
1 5
1 2
4 5
1 3
2 2
1 2
3 5
2 5
2 5
2 5
1 3
3 5
3 5
2 3
4 5
1 5
1 2
4 5
2 2
4 5
1 4
3 5
4 4
3 3
2 5
2 3
1 1
3 5
1 4
1 3
2 5
1 4
3 4
3 4
2 5
1 4
2 3
1 3
2 2
1 3
3 5
2 5
3 4
1 5
1 2
2 3
3 3
2 2
1 4
1 1
1 3
4 4
2 3
2 4
1 2
3 3
3 4
4 5
1 5
2 2
4 5
3 4
2 3
2 4
3 5
1 2
5 5
3 4
2 4
1 3
3 4
1 5
1 2
1 5
1 5
4 5
1 2
5 5
1 3
1 5
1 5
3 5
1 4
2 5
2 5
1 4
2 3
1 4
3 4
1 5
1 5
5 5
2 3
3 5
3 4
3 4
1 3
5 5
3 5
3 5
1 2
3 3
1 1
1 4
3 5
3 4
2 3
1 4
1 1
1 3
3 4
2 3
2 4
1 4
1 1
1 2
2 3
1 4
4 5
2 4
1 4
4 4
5 5
3 3
3 3
1 5
1 5
2 4
3 3
3 5
1 4
2 3
2 4
1 4
2 2
2 5
2 5
1 2
1 2
3 5
2 5
2 4
1 5
2 3
1 5
4 5
1 1
3 5
3 5
5 5
2 2
1 2
1 2
3 4
3 4
1 3
2 4
3 3
3 5
4 5
1 4
4 5
3 4
2 2
3 4
3 3
3 5
3 3
5 5
2 4
3 4
3 5
2 4
2 3
1 3
2 5
1 5
1 4
3 5
1 3
1 3
3 4
1 2
5 5
1 2
1 3
3 3
4 5
2 4
2 4
4 5
1 3
2 3
3 5
3 5
2 5
3 3
3 5
4 5
1 3
5 5
1 5
3 4
1 1
3 5
1 3
4 4
3 5
5 5
3 4
4 5
1 2
2 2
3 4
4 5
2 5
2 5
1 4
1 3
2 3
2 3
2 3
2 3
5 5
2 5
3 5
2 5
2 4
2 4
3 5
2 4
2 3
2 5
1 4
4 5
2 5
1 3
3 3
2 5
1 5
4 5
2 5
1 4
1 4
2 5
1 2
2 3
2 3
1 3
3 5
1 3
2 4
1 2
4 5
2 3
3 4
1 5
4 5
1 2
1 3
4 5
5 5
1 1
3 4
1 4
2 4
1 3
3 3
3 5
3 3
5 5
4 5
1 2
1 5
2 4
1 4
1 3
2 4
1 2
1 3
3 5
1 3
3 4
2 3
2 3
1 5
1 3
4 5
3 3
1 4
1 3
3 5
4 5
1 1
1 3
4 4
4 5
1 5
1 3
5 5
1 3
3 4
4 4
4 4
3 5
2 5
1 2
1 4
1 3
3 3
1 5
2 3
1 2
3 5
2 3
1 2
3 5
2 5
4 5
2 4
2 5
2 2
4 4
4 4
3 3
1 2
4 5
3 4
4 4
3 4
2 3
1 5
1 4
1 5
3 5
2 5
3 4
3 4
2 4
2 5
1 5
3 5
1 5
2 5
3 3
1 1
2 3
4 5
1 3
1 1
1 3
5 5
4 4
5 5
1 5
3 5
3 5
3 4
3 4
1 1
2 4
1 5
1 1
1 5
1 3
1 5
5 5
2 4
1 3
2 5
1 5
2 3
4 4
5 5
1 3
2 3
1 2
3 4
2 4
2 3
1 2
2 4
1 3
3 4
3 4
3 3
2 4
3 5
1 5
4 4
5 5
3 4
1 2
4 4
1 3
4 4
1 5
2 3
2 4
4 5
5 5
2 5
1 2
5 5
2 4
2 4
3 4
3 4
1 4
2 5
2 3
1 2
1 3
3 3
3 4
4 4
4 4
2 5
3 4
5 5
1 3
2 3
2 5
1 4
1 2
3 4
2 3
2 5
2 3
3 3
4 4
2 4
4 4
1 4
4 5
1 5
3 4
1 3
3 3
3 5
2 4
1 4
2 4
1 3
1 3
3 5
3 4
1 4
1 2
1 4
2 3
3 5
1 3
2 2
1 1
1 1
1 1
2 5
2 5
1 4
2 5
1 3
4 5
3 4
2 4
1 5
1 3
1 3
2 3
3 4
2 5
1 3
2 4
1 2
1 5
4 5
2 2
3 4
3 5
2 3
1 1
2 4
2 5
3 5
1 3
4 5
1 5
1 2
1 3
4 5
4 5
2 3
1 5
1 3
1 3
1 3
1 3
1 5
2 5
5 5
1 5
2 4
1 3
1 5
3 5
1 3
2 5
2 4
2 4
3 5
2 4
3 4
1 3
1 5
4 5
3 4
1 2
1 1
1 4
1 2
1 4
2 3
1 3
4 4
3 3
3 4
2 3
2 3
1 2
1 1
2 3
3 3
1 5
2 2
1 1
1 1
1 4
3 5
1 2
1 4
3 5
1 2
2 4
4 5
1 3
2 5
1 2
1 3
4 5
3 3
4 4
1 5
2 3
2 5
5 5
1 4
1 3
5 5
1 4
3 3
1 4
2 5
4 5
2 5
1 2
5 5
1 1
1 5
4 5
3 4
4 4
1 5
2 3
1 5
2 5
2 4
2 3
3 4
1 2
2 4
3 4
1 4
1 3
2 4
4 5
1 2
1 5
4 5
3 4
5 5
1 4
1 1
1 4
1 4
1 2
2 2
1 5
2 3
2 3
1 5
1 4
3 4
2 5
4 5
2 5
2 4
4 5
2 4
5 5
1 2
2 3
3 4
2 4
1 2
1 4
1 5
1 2
1 5
3 5
3 4
3 4
3 3
1 4
2 3
3 4
2 3
3 4
3 5
1 3
4 4
2 4
2 3
2 4
4 4
4 4
4 5
3 5
2 4
1 5
1 2
1 2
2 5
2 4
1 4
3 5
3 4
2 4
4 4
2 3
2 4
2 5
2 4
1 4
2 4
4 4
3 3
1 5
1 4
3 4
3 4
1 4
1 3
3 4
2 2
3 5
1 5
2 4
1 4
4 5
2 2
2 5
3 4
1 3
1 4
3 3
2 3
2 4
4 4
4 4
1 2
3 4
1 4
1 2
2 4
4 4
1 3
1 4
4 4
1 4
5 5
1 5
2 5
1 3
1 5
1 1
2 2
4 5
2 3
4 5
3 3
4 5
2 2
1 5
1 4
4 5
4 5
2 5
4 5
2 2
5 5
3 5
4 5
4 4
3 3
1 2
2 2
5 5
2 5
2 3
4 5
2 4
2 3
4 5
4 5
3 5
4 5
1 2
4 4
2 5
4 5
3 3
1 2
3 4
1 3
1 3
2 4
2 4
2 3
1 3
3 4
2 3
3 5
3 4
2 4
5 5
3 4
3 3
3 3
4 5
3 3
3 5
2 2
2 5
4 5
2 4
2 4
1 3
3 5
1 2
1 4
1 4
2 3
1 5
2 4
3 4
3 5
2 5
1 5
1 5
5 5
2 2
5 5
1 2
1 5
3 4
2 4
2 4
3 4
1 3
1 5
5 5
1 5
2 5
1 1
1 2
2 4
2 4
1 4
2 4
2 5
2 4
3 4
4 5
4 5
1 2
3 4
3 4
1 1
2 3
3 5
3 3
2 4
1 1
2 5
2 4
1 2
4 4
2 5
3 4
4 5
1 3
3 5
2 2
2 5
1 5
3 5
1 1
2 3
4 5
3 4
3 5
2 4
2 4
1 1
1 5
2 4
2 5
2 3
2 3
3 4
1 5
1 4
2 4
2 5
5 5
5 5
1 2
1 4
4 4
1 2
2 3
1 4
2 3
2 5
3 5
1 4
2 5
1 1
1 2
4 5
2 3
1 2
3 3
4 5
3 4
1 3
2 3
1 5
3 3
1 2
1 4
1 3
1 4
1 1
3 3
2 5
1 5
3 3
1 4
3 4
1 5
1 2
2 4
2 3
2 5
1 1
1 4
2 3
5 5
4 4
2 4
4 5
5 5
3 4
2 4
2 3
1 4
2 5
2 5
4 5
4 5
2 5
5 5
3 5
3 3
1 2
1 1
3 4
5 5
2 5
4 5
3 4
1 3
4 4
1 4
3 5
2 4
3 4
3 3
2 2
4 4
5 5
1 3
4 5
2 3
4 4
2 5
1 4
5 5
1 3
2 5
4 5
1 5
1 3
3 5
2 4
1 4
3 4
4 5
1 3
2 4
3 3
1 3
2 5
1 3
1 2
3 4
1 1
3 5
3 4
5 5
2 2
3 5
1 2
3 5
2 3
1 5
4 5
1 2
1 4
1 3
2 5
1 3
2 4
1 2
1 4
1 3
2 4
2 4
2 5
3 5
1 2
1 5
1 2
1 3
4 5
3 5
4 5
3 3
1 2
1 2
2 4
1 2
5 5
3 4
1 2
1 2
2 3
1 3
1 3
3 5
4 4
2 4
4 4
1 2
3 3
5 5
1 2
1 1
5 5
3 4
3 5
4 5
2 3
1 3
1 4
1 3
4 5
2 5
3 4
2 5
1 5
4 4
1 2
1 5
4 4
2 2
1 2
4 5
4 4
1 5
5 5
1 2
2 4
4 5
1 2
1 2
1 1
2 3
2 5
1 3
4 4
1 5
2 4
3 5
1 5
2 5
2 3
1 4
2 5
1 4
1 5
4 5
4 5
1 4
2 2
4 4
2 5
2 4
2 3
1 1
2 3
1 3
2 3
1 2
2 2
1 4
3 3
2 4
1 2
4 5
1 5
1 5
1 5
3 4
1 5
2 5
3 5
1 4
2 4
2 5
2 4
3 5
2 4
1 4
1 5
1 5
4 4
1 1
3 4
2 3
1 3
3 3
1 4
1 5
3 5
2 2
1 4
4 5
2 3
1 3
5 5
2 4
1 2
2 4
5 5
5 5
3 5
2 5
2 4
1 4
2 5
3 5
3 5
2 3
4 4
1 3
4 5
2 4
1 1
3 5
1 3
1 3
2 5
1 5
3 4
2 2
1 1
4 5
4 5
1 5
3 4
3 4
2 3
2 4
3 4
3 5
5 5
1 3
3 3
1 1
2 2
3 5
1 4
3 5
2 5
1 4
1 3
1 4
1 2
2 2
4 5
5 5
4 5
1 1
4 5
2 5
1 1
1 2
4 5
1 2
1 3
3 4
1 3
4 5
2 3
5 5
2 2
1 5
1 4
3 3
2 4
2 4
1 2
2 5
1 3
3 3
3 5
1 3
3 5
3 3
4 5
2 3
2 4
4 5
2 3
1 5
4 4
3 5
3 4
1 5
5 5
1 5
1 4
2 3
4 5
2 4
3 5
4 4
2 4
3 4
2 5
3 5
2 3
2 4
3 5
3 3
2 5
1 2
3 5
1 3
2 2
1 2
4 4
1 2
1 1
1 5
2 5
3 5
3 5
3 4
2 5
1 2
1 1
2 4
1 3
2 4
1 4
2 2
2 3
1 4
2 3
4 5
2 5
5 5
1 3
3 5
1 4
2 3
3 4
5 5
1 5
3 5
3 4
2 4
4 5
1 1
2 3
1 3
4 5
3 4
2 3
3 4
3 3
3 3
1 2
1 5
2 4
1 5
4 5
1 5
3 3
3 5
3 5
1 3
1 4
3 5
2 4
4 4
3 5
1 1
3 4
1 4
3 4
5 5
3 4
1 5
3 4
3 4
2 4
3 3
3 5
1 5
3 5
3 5
2 4
4 5
1 2
4 5
1 5
1 2
1 5
4 4
1 4
4 4
1 4
2 5
2 4
1 3
2 4
2 5
3 5
3 5
2 2
2 4
2 5
3 5
3 5
1 3
2 3
4 4
2 3
1 3
2 2
1 2
3 5
5 5
3 5
2 4
4 5
2 2
3 4
1 2
2 4
4 4
1 2
2 4
2 5
5 5
3 5
1 1
1 2
2 3
3 4
1 1
2 3
1 4
2 5
1 3
2 4
4 5
1 4
1 5
1 4
3 5
1 4
1 4
4 5
5 5
1 5
2 4
2 2
5 5
1 3
3 5
3 5
2 5
1 3
2 3
1 4
1 2
4 4
2 2
3 5
1 3
3 3
1 1
3 4
2 2
3 3
2 4
3 3
1 3
3 5
4 5
3 5
4 4
2 3
3 4
1 3
3 5
2 4
1 4
1 2
1 2
5 5
1 3
2 4
4 4
4 4
2 5
3 3
2 3
1 1
1 1
2 3
4 4
1 5
4 4
3 3
1 2
3 3
3 4
4 5
1 5
1 5
4 5
1 4
3 4
4 5
4 4
3 3
2 3
1 5
3 3
1 2
3 4
1 2
5 5
2 2
5 5
1 4
4 5
1 1
2 2
2 3
4 5
4 5
5 5
1 4
3 5
1 4
2 4
1 3
2 2
1 2
1 5
2 3
1 2
1 1
1 2
2 3
1 4
4 4
5 5
1 3
3 4
3 4
1 5
1 2
1 5
1 2
2 3
4 5
3 4
2 4
4 5
3 4
4 5
1 4
5 5
1 3
2 4
3 5
1 3
2 4
1 2
3 5
2 5
1 4
2 5
1 4
5 5
1 1
2 4
3 3
2 3
2 5
3 5
2 3
3 4
3 5
3 4
4 5
1 1
4 4
1 3
2 5
2 2
1 5
4 5
1 4
3 3
3 5
4 5
3 5
2 3
2 2
2 4
1 1
3 5
2 3
4 4
4 4
3 3
1 4
2 4
1 3
3 3
1 2
4 5
1 3
4 4
2 4
4 5
1 4
2 4
1 1
1 4
4 5
1 1
1 2
1 5
1 4
1 1
3 5
2 5
2 4
2 4
3 5
1 1
5 5
4 5
1 2
2 2
2 2
2 5
2 5
3 5
2 4
1 5
1 1
1 5
2 4
2 3
2 2
2 3
3 5
2 4
2 4
3 4
2 5
2 2
1 3
3 4
2 4
1 4
1 3
2 3
2 2
1 4
3 5
1 2
2 5
4 4
2 5
2 3
3 5
4 4
1 5
1 4
2 4
5 5
1 2
2 4
4 4
1 3
3 5
3 4
1 5
1 4
2 2
1 1
3 4
4 4
1 1
3 5
4 4
1 4
2 5
2 2
1 2
1 5
2 3
1 2
2 3
1 4
3 3
1 3
1 5
2 4
2 4
3 4
2 5
3 5
4 5
5 5
3 4
1 4
1 3
1 4
4 4
2 5
2 3
1 5
2 5
1 2
2 5
3 3
1 3
1 2
4 5
1 4
4 5
5 5
1 5
1 3
1 5
4 4
1 4
4 5
3 5
1 4
5 5
3 4
5 5
1 1
2 4
1 4
4 5
3 3
3 4
2 5
1 1
1 5
4 5
2 5
1 4
1 4
2 5
3 4
1 1
2 2
1 3
1 4
1 1
4 5
1 2
3 5
4 5
2 5
2 3
3 5
1 3
3 4
2 4
1 5
2 2
4 5
5 5
1 1
1 4
4 4
1 3
3 3
3 4
1 5
4 4
3 4
1 3
2 3
1 5
4 5
1 3
1 2
2 4
2 2
4 5
4 4
3 3
1 5
4 5
4 5
3 5
2 3
2 3
3 3
1 3
1 4
3 4
3 4
1 5
1 2
2 5
3 4
3 5
1 4
1 4
1 2
1 5
2 5
4 5
1 1
3 3
5 5
1 3
4 5
3 4
3 3
3 5
2 3
1 5
3 3
4 4
3 4
1 5
1 2
3 4
1 5
4 4
2 3
4 5
3 4
2 3
2 5
3 5
2 4
1 2
1 4
1 2
1 2
2 5
2 2
2 4
3 5
1 1
4 5
3 5
1 1
4 5
2 3
1 4
1 2
1 3
1 2
2 5
1 4
4 4
2 3
4 5
1 3
1 5
3 4
3 4
3 4
2 3
4 5
1 3
3 5
1 1
3 5
3 5
1 2
2 2
2 3
2 4
2 4
1 2
3 5
4 5
1 1
1 1
1 2
2 4
1 2
1 1
2 4
3 3
1 4
1 4
2 2
2 5
2 3
5 5
3 4
1 1
1 2
1 1
1 5
1 4
4 4
1 5
1 4
2 4
3 5
1 2
1 4
4 4
2 5
1 5
1 1
3 4
3 5
2 2
2 4
4 4
4 5
2 4
4 4
1 4
4 5
3 4
5 5
3 3
2 4
3 3
2 3
2 4
1 2
1 4
2 2
3 3
2 5
3 3
2 3
1 1
4 5
4 4
1 2
4 4
4 4
1 2
2 2
3 4
3 4
1 5
1 1
2 5
1 4
1 5
1 2
2 4
1 1
2 4
2 4
2 5
4 5
1 4
3 4
2 3
4 4
3 5
2 4
2 4
1 5
1 3
4 5
4 4
1 4
4 5
2 5
1 3
1 4
3 4
2 3
2 5
2 2
1 4
1 1
2 5
2 3
1 5
4 5
1 3
3 5
1 2
2 5
4 5
3 3
2 5
2 2
2 3
1 2
1 4
5 5
1 3
4 5
3 4
1 5
1 5
1 2
4 5
1 2
2 3
2 4
4 4
1 1
1 3
1 1
2 4
3 4
3 4
3 5
2 5
1 1
3 4
2 2
1 4
1 1
1 1
1 3
2 5
2 5
2 3
1 5
2 5
1 5
3 3
2 5
1 5
2 3
1 5
3 4
2 3
1 4
1 5
1 3
2 2
4 4
3 5
1 3
1 3
1 4
2 3
3 5
4 4
3 5
2 3
1 2
2 3
1 4
2 4
2 3
2 4
4 5
1 4
1 4
1 4
1 2
2 5
3 4
4 4
3 5
2 4
2 4
1 2
3 3
1 2
1 2
3 3
2 4
2 4
4 5
2 2
1 4
1 5
1 4
2 4
1 5
4 5
1 2
3 5
1 3
2 5
1 5
1 5
1 4
2 4
1 4
2 4
1 1
1 2
1 2
2 5
3 3
1 4
1 1
2 5
2 4
1 1
2 3
2 5
1 2
5 5
1 2
1 2
2 4
3 5
5 5
1 5
2 2
3 5
2 3
1 3
1 2
2 2
3 5
1 2
1 2
3 5
3 5
4 5
1 4
1 4
1 4
1 5
5 5
2 4
5 5
1 3
1 4
2 2
1 5
1 2
1 3
2 5
4 5
2 5
3 3
2 4
3 5
5 5
1 5
3 5
2 5
4 5
3 3
3 4
1 4
2 3
1 5
1 5
4 4
2 4
3 4
4 5
2 4
2 2
2 4
2 3
2 3
1 4
3 5
3 5
3 5
4 5
3 5
1 3
1 2
1 1
2 2
1 4
4 5
2 4
2 2
2 4
3 3
1 5
1 3
2 2
2 5
5 5
3 5
1 3
4 4
4 5
1 1
3 3
1 5
1 1
2 4
1 2
1 5
1 4
2 4
1 3
2 4
3 4
2 5
2 4
3 4
1 1
3 3
3 4
4 4
1 5
3 4
2 2
2 4
3 5
2 5
4 5
1 5
2 3
2 3
3 3
2 5
2 2
3 4
1 5
2 2
1 1
1 4
2 5
2 4
2 3
3 5
3 5
2 3
1 5
1 3
3 5
2 4
2 3
1 3
2 5
4 5
1 3
1 5
3 5
2 4
4 4
1 2
5 5
1 2
2 3
3 4
2 3
5 5
3 4
1 2
1 5
1 4
3 4
1 5
2 3
4 5
5 5
2 5
2 5
1 5
1 1
2 5
3 3
2 3
3 5
3 5
3 4
1 2
3 4
2 4
2 3
1 2
2 3
2 3
1 3
1 4
4 4
2 2
2 5
3 4
1 5
1 5
2 2
2 4
2 4
1 3
1 5
1 1
3 4
1 1
2 5
1 3
2 4
2 2
1 2
1 4
1 1
3 5
1 2
1 3
4 5
3 4
2 4
4 4
5 5
1 5
1 3
4 4
4 5
1 3
2 2
2 4
1 1
3 5
1 5
1 4
2 5
1 3
2 3
2 5
3 4
2 3
1 5
2 3
2 4
2 3
2 5
1 2
1 4
1 3
3 4
1 3
2 3
1 1
1 5
1 1
2 5
2 5
1 5
1 2
2 3
3 5
2 3
4 5
5 5
3 3
1 4
4 4
2 2
4 5
4 5
1 5
2 2
4 5
2 2
2 2
4 5
3 5
5 5
1 3
1 3
1 2
3 4
5 5
2 4
2 5
1 4
3 5
4 5
1 3
3 4
2 5
1 4
4 5
3 4
3 5
1 2
2 4
1 2
2 3
1 2
1 4
1 4
2 5
4 4
1 3
1 3
1 1
1 4
1 3
1 2
3 3
2 4
1 5
2 3
5 5
2 5
2 3
1 5
3 4
4 5
1 5
2 2
3 4
3 3
2 4
1 4
1 3
2 5
1 1
4 5
2 3
2 3
1 1
3 3
2 3
3 5
3 5
1 1
1 4
2 5
1 4
1 2
1 2
2 4
2 3
1 4
2 2
1 1
4 5
2 4
2 4
2 5
4 4
1 3
3 3
1 2
1 5
3 4
1 3
4 5
1 2
2 5
3 3
2 3
3 5
2 5
1 3
1 1
2 4
1 2
1 2
1 2
1 3
5 5
1 3
1 2
2 3
2 4
1 4
1 3
5 5
2 3
2 2
1 2
3 3
1 1
5 5
5 5
1 5
1 4
1 3
2 4
3 4
2 3
3 4
2 5
1 3
1 4
1 5
5 5
4 5
1 5
1 1
4 5
1 4
3 5
2 3
3 5
2 5
3 5
2 4
1 3
1 5
1 4
3 4
3 5
1 5
1 5
1 5
3 4
4 4
1 3
1 3
3 4
5 5
3 5
1 3
1 4
2 4
1 4
2 4
1 5
1 1
2 2
3 5
2 3
3 4
1 1
3 4
3 3
5 5
3 4
3 5
3 5
2 2
2 4
2 4
1 4
1 5
1 4
3 4
2 5
1 3
1 5
4 5
2 2
3 5
1 5
1 2
3 5
2 5
1 5
1 5
1 4
2 5
2 4
2 2
1 3
1 2
3 5
1 2
2 2
1 5
1 5
4 5
2 3
1 4
1 2
2 3
1 4
2 2
2 4
4 4
3 5
4 5
2 3
2 2
2 3
2 3
1 3
5 5
3 4
2 5
2 5
3 5
1 5
4 5
1 3
4 4
1 1
3 5
4 5
1 5
1 5
5 5
5 5
1 1
1 5
5 5
1 5
2 5
3 5
1 2
1 1
1 2
3 3
1 3
2 5
5 5
1 3
1 5
1 1
1 3
3 4
1 5
3 5
1 3
2 3
2 2
2 5
3 4
3 3
3 4
3 4
2 3
2 3
3 5
1 4
2 4
2 5
4 5
2 5
1 4
4 5
2 4
5 5
2 4
2 4
2 4
1 5
1 3
2 4
1 2
3 5
4 5
1 3
1 2
1 4
1 2
1 5
1 4
3 3
3 4
4 5
2 3
1 5
1 3
4 4
3 3
2 2
2 3
1 2
2 4
1 3
3 5
1 2
1 4
2 4
1 3
3 5
3 5
3 4
3 5
3 5
1 5
2 5
4 4
3 4
1 1
2 2
1 4
2 5
5 5
3 3
1 2
2 2
4 5
2 5
2 3
3 5
4 4
2 4
1 3
3 4
3 5
5 5
1 4
1 2
1 2
4 5
3 5
1 5
3 5
1 3
4 5
1 5
1 5
3 4
3 4
3 3
3 5
3 4
1 1
1 3
2 5
1 3
3 4
1 5
1 4
2 3
2 5
1 4
5 5
1 2
1 5
3 3
2 3
3 5
2 4
2 2
1 3
1 5
2 5
1 3
5 5
2 2
1 2
2 3
4 5
2 5
2 3
5 5
3 5
2 4
4 5
2 4
1 5
1 4
1 4
3 5
3 5
1 2
1 5
1 1
1 5
4 4
4 4
5 5
1 3
4 5
1 4
1 1
1 2
4 4
1 3
1 4
3 4
3 5
3 3
1 3
2 5
4 5
1 3
2 2
1 5
2 3
1 4
1 5
1 2
3 5
1 4
3 5
1 2
4 4
1 1
2 5
3 5
2 2
3 3
3 4
2 3
1 4
1 5
4 4
3 5
1 3
2 3
2 4
3 5
4 4
3 3
1 4
1 5
1 3
3 5
1 2
4 5
2 2
2 3
1 5
2 3
1 4
3 5
3 5
2 5
1 4
1 2
3 4
1 5
2 3
4 5
4 5
1 5
2 5
3 3
3 3
3 3
4 5
2 4
4 5
3 5
3 4
5 5
1 2
1 1
1 3
2 5
3 5
3 4
1 3
2 2
2 5
2 2
2 5
3 5
2 5
2 4
2 3
1 3
2 3
2 5
1 1
1 2
2 4
2 3
1 2
1 3
1 5
5 5
2 3
2 4
1 3
1 2
1 3
1 5
2 4
4 5
3 4
3 5
5 5
2 5
1 5
2 5
2 4
1 2
1 2
1 4
1 1
1 5
1 1
2 4
1 4
2 3
4 5
2 5
2 3
1 2
3 5
4 5
1 1
5 5
4 5
1 1
1 2
2 5
3 5
3 4
3 4
1 2
2 5
4 5
1 2
2 4
3 4
4 5
1 4
1 3
3 3
2 3
1 4
2 3
1 2
4 5
1 2
1 4
1 4
2 3
4 5
4 4
1 1
2 3
3 4
2 3
1 4
2 3
1 1
1 3
1 3
2 3
5 5
3 4
1 4
1 2
2 3
1 2
1 4
5 5
1 5
2 3
1 5
1 4
2 4
3 4
1 1
3 3
5 5
4 5
2 3
1 5
2 3
2 2
2 5
1 4
3 4
1 2
1 2
4 4
2 2
3 3
3 5
5 5
2 5
3 5
2 3
1 2
4 5
3 3
3 4
3 4
2 2
2 2
3 5
3 4
1 1
4 5
1 2
2 4
3 5
1 4
5 5
1 3
1 5
4 5
1 4
2 2
3 5
1 4
1 3
2 3
2 2
1 3
1 3
1 5
4 4
3 5
3 3
3 3
4 4
4 4
1 5
4 4
4 5
3 3
4 5
3 5
1 1
4 5
2 3
1 4
2 5
2 5
5 5
4 5
3 5
1 2
2 3
1 3
2 2
1 3
4 5
4 4
1 3
3 4
1 2
1 5
3 4
1 5
2 2
1 2
1 3
3 4
1 5
2 2
2 2
2 3
5 5
1 2
1 4
2 4
1 5
2 4
2 3
2 5
2 4
4 5
3 4
1 3
2 2
1 5
1 2
2 5
3 3
5 5
2 4
3 3
1 1
1 2
2 3
3 4
1 4
3 3
3 5
3 5
2 4
4 5
5 5
1 4
1 3
2 2
1 5
3 4
1 3
1 5
3 4
1 4
1 2
3 3
4 5
2 3
2 2
2 5
1 5
3 5
2 5
1 2
3 4
2 4
2 4
2 5
3 4
1 2
2 2
1 2
1 5
2 5
4 5
1 2
3 4
2 5
2 4
2 5
4 4
1 3
2 2
1 3
2 5
3 5
3 4
2 5
3 5
3 5
4 4
1 3
1 5
3 5
4 5
2 4
1 4
1 2
2 5
3 5
3 5
1 3
2 4
2 3
1 5
1 2
1 5
3 5
1 2
3 4
3 3
3 5
2 4
2 4
2 5
1 5
1 2
1 2
3 4
1 3
1 2
1 3
3 5
2 4
1 4
1 5
4 5
2 5
5 5
2 5
1 5
1 5
2 4
2 3
1 5
1 2
1 4
3 5
1 3
3 4
3 4
2 3
3 5
3 5
2 4
3 4
3 4
2 3
1 5
2 5
1 3
2 2
4 5
4 4
1 4
2 5
2 3
2 5
4 5
2 4
3 5
4 5
1 4
3 3
1 4
2 5
1 4
2 3
4 5
3 5
3 4
2 3
2 2
1 4
2 3
3 3
4 5
1 4
3 3
2 4
4 5
1 3
1 4
4 5
4 5
4 5
3 4
3 4
2 4
1 5
2 5
2 4
2 2
3 5
3 5
3 5
4 4
3 5
1 2
3 5
5 5
1 2
3 4
3 5
2 3
1 2
1 4
5 5
2 5
1 2
1 5
2 2
2 4
2 4
3 4
1 1
1 2
1 5
5 5
2 2
4 5
1 5
1 3
4 5
1 2
1 3
2 4
1 3
2 3
3 3
2 5
4 5
1 4
3 5
3 5
3 5
4 5
1 2
5 5
3 5
3 4
1 5
1 2
1 3
2 3
4 5
4 4
4 4
1 2
2 2
4 5
1 5
3 5
3 3
1 3
2 2
1 5
3 3
1 5
3 5
2 4
2 5
2 5
2 4
1 1
2 5
2 3
1 3
2 5
4 5
3 4
1 5
1 4
4 5
1 2
1 5
3 5
3 5
2 5
1 3
1 2
1 3
1 1
1 3
1 4
1 5
3 3
4 4
3 5
3 3
1 3
2 5
1 2
Expected Output
3
1
2
2
2
1
2
1
2
2
1
1
1
1
1
2
1
1
1
2
1
1
1
3
3
2
2
3
1
2
1
1
1
1
2
1
2
2
2
2
2
1
2
1
1
2
1
2
2
1
1
1
1
1
2
2
1
2
1
1
1
2
1
1
2
1
1
2
1
1
2
1
3
3
2
2
1
2
1
3
1
2
1
1
2
2
1
2
1
1
1
2
2
1
2
1
2
1
2
3
2
1
1
1
1
3
2
1
1
1
2
1
1
1
2
2
2
2
1
2
1
2
1
1
2
2
2
2
1
1
1
1
1
2
3
2
2
2
1
2
2
2
2
1
3
1
2
1
1
2
1
1
1
2
2
3
3
2
3
1
1
1
1
1
1
2
1
1
1
3
1
1
2
3
2
1
2
1
1
1
2
1
1
1
2
1
2
1
3
1
2
1
2
1
3
2
1
2
1
1
1
1
1
1
1
2
2
2
1
2
1
1
1
1
1
1
1
2
2
2
3
2
1
1
1
1
2
3
2
3
1
1
2
1
2
2
2
3
1
1
2
1
1
2
2
2
1
1
3
2
2
1
1
2
3
1
2
1
1
1
2
1
2
3
1
1
2
2
1
2
1
1
3
2
1
1
2
2
2
1
2
1
1
1
3
1
2
1
2
2
1
1
1
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
3
1
1
1
2
1
2
2
2
2
1
1
1
2
2
1
1
2
2
2
1
1
1
1
2
2
2
1
2
2
1
1
1
1
1
1
2
1
2
2
2
2
1
1
2
2
1
2
1
3
1
2
2
2
1
2
2
2
1
2
2
1
1
2
1
1
2
1
1
2
2
1
1
2
2
2
2
2
2
2
2
3
2
2
1
1
1
3
2
1
2
3
2
2
1
1
2
2
1
3
1
3
2
1
1
1
1
2
3
2
1
2
3
2
1
2
1
1
1
2
3
1
2
1
1
1
2
3
2
2
1
1
1
2
2
1
2
1
2
1
2
3
1
2
1
2
2
3
1
1
2
2
2
1
1
2
3
2
2
1
1
1
1
2
3
1
1
2
2
2
1
1
2
3
2
1
2
2
1
1
1
1
2
2
3
1
1
2
1
1
2
2
1
2
2
2
2
2
1
1
2
1
1
1
1
1
1
1
1
2
2
1
1
1
1
1
2
1
1
1
2
1
1
1
2
1
2
1
2
1
2
2
2
1
2
2
2
1
2
2
2
1
2
2
2
2
1
1
1
1
2
2
2
2
2
1
2
1
2
1
3
1
2
2
1
3
3
1
1
1
2
1
1
3
2
1
3
1
1
1
1
1
3
1
2
1
1
2
2
1
1
1
1
1
2
1
1
2
1
1
3
2
1
3
1
2
1
1
2
2
2
1
3
1
1
1
1
3
2
1
1
2
1
1
2
1
2
1
1
1
3
1
2
1
1
1
1
2
1
2
3
2
1
1
2
2
2
1
2
2
2
1
1
2
1
1
1
1
3
1
1
3
1
3
2
1
1
2
2
1
3
3
1
2
1
2
2
1
3
3
1
2
1
1
1
2
3
1
2
1
2
1
1
1
2
1
1
1
1
1
1
1
2
2
1
2
1
2
2
2
1
2
1
1
1
1
2
1
1
1
2
2
1
2
2
1
2
1
1
2
1
1
1
1
2
3
2
2
2
1
1
1
1
1
1
1
1
2
2
1
2
2
2
1
1
1
3
2
1
3
1
1
1
1
1
3
1
1
1
1
1
1
2
2
1
2
2
2
2
2
2
2
1
1
3
1
1
2
2
2
2
1
1
1
1
1
1
2
1
2
1
2
1
1
2
2
1
1
1
1
1
1
1
1
2
1
2
1
2
1
2
1
2
2
1
1
2
2
2
2
2
1
2
1
1
1
1
2
1
1
1
2
2
2
1
2
1
2
2
1
1
1
3
3
1
1
2
1
2
1
2
1
1
2
1
2
1
3
2
1
1
1
1
2
1
3
1
2
2
2
2
1
1
2
1
1
2
3
2
2
1
2
3
1
1
2
1
2
2
1
2
1
1
2
2
1
1
1
2
1
1
2
1
2
2
2
1
1
2
1
1
1
1
1
1
2
1
3
1
1
1
1
1
2
1
2
2
1
2
3
1
2
1
3
1
1
1
2
1
1
1
2
1
1
2
2
2
2
1
3
3
2
3
1
2
2
2
1
3
2
1
1
2
2
2
1
2
1
1
3
1
1
2
1
1
1
2
3
1
1
2
3
1
2
1
2
2
1
1
2
2
2
2
2
1
1
1
1
1
2
3
2
1
2
1
1
1
2
1
3
2
1
1
2
2
1
2
3
1
1
1
2
1
2
1
2
2
2
2
1
1
1
1
2
1
2
2
1
1
2
1
2
1
2
2
2
2
2
3
1
1
2
2
2
3
2
2
2
2
1
3
2
1
1
2
2
2
2
2
2
1
2
2
1
1
2
2
1
2
1
2
1
1
3
2
2
2
3
2
1
2
1
2
2
1
1
1
1
1
2
1
1
1
1
1
2
2
2
2
3
1
1
1
1
1
1
1
1
1
2
1
2
1
1
2
2
3
2
1
1
2
1
1
1
3
1
1
2
2
3
1
2
2
1
1
3
2
2
2
1
1
1
1
2
1
2
1
1
1
2
1
1
1
2
2
1
2
1
2
2
1
3
2
1
2
1
1
1
1
1
1
3
1
1
1
2
3
1
2
2
1
2
1
1
2
2
1
1
1
2
2
2
1
1
1
1
1
2
2
1
1
2
3
2
1
1
2
3
2
3
3
2
1
2
1
1
2
1
2
2
1
2
1
1
2
1
1
2
1
2
2
1
1
2
3
2
1
2
2
2
1
1
1
3
2
1
1
1
2
1
2
1
2
1
2
1
2
3
1
1
1
1
2
2
1
2
1
1
1
1
2
1
1
2
3
1
3
2
2
2
1
2
2
1
2
2
2
2
1
2
2
2
2
2
1
3
3
2
1
1
2
1
1
2
1
1
1
1
1
1
1
2
1
2
1
1
1
2
1
2
1
2
2
1
2
2
2
1
1
1
1
2
1
3
3
1
3
1
2
2
2
2
2
2
1
2
1
3
2
2
1
3
1
1
2
2
2
2
1
1
2
2
2
1
1
2
1
1
1
1
1
2
1
1
2
1
1
2
3
3
1
3
2
2
2
2
3
1
2
2
3
1
3
2
1
3
1
1
1
2
2
1
2
1
1
2
1
1
2
2
2
2
2
1
2
3
1
1
1
1
3
1
1
2
3
1
2
2
3
1
1
2
1
1
2
1
2
2
1
3
2
1
1
2
2
1
1
2
1
1
1
1
1
1
2
2
1
1
1
2
1
1
2
2
1
1
2
2
1
2
2
1
1
2
3
2
1
1
1
1
2
1
2
1
1
1
1
1
1
2
1
1
1
1
1
2
2
1
1
1
2
2
1
1
2
1
1
2
2
1
2
1
3
1
2
1
2
2
1
1
1
1
3
1
3
2
1
2
1
2
2
1
1
1
2
2
2
1
1
1
2
2
1
2
3
1
2
3
1
1
1
1
2
3
1
2
1
1
2
1
1
2
2
1
2
3
1
1
1
3
1
1
1
1
2
1
2
2
2
3
1
1
1
2
1
1
1
1
1
1
2
3
1
2
1
1
1
2
1
2
1
3
2
2
1
2
1
2
2
1
2
2
1
1
1
1
1
1
1
3
1
2
2
2
2
1
1
2
2
1
3
3
1
1
1
2
1
1
1
1
1
2
1
1
1
3
1
1
2
1
1
2
1
1
1
2
1
2
1
1
1
2
2
2
2
1
1
3
2
2
1
2
1
3
1
3
1
1
2
2
1
1
2
1
2
2
2
1
2
1
3
1
2
1
3
1
1
2
1
1
1
1
1
1
1
1
2
2
1
1
2
2
2
1
2
3
1
1
1
2
2
1
1
1
1
1
1
2
1
2
1
3
2
1
1
1
2
1
2
2
1
1
2
1
1
1
2
2
1
2
1
1
2
2
2
2
3
2
1
1
1
1
1
2
1
2
2
1
2
2
3
2
1
2
1
2
1
1
2
2
1
2
1
2
1
2
1
1
1
3
3
1
1
2
2
1
2
2
1
3
1
1
1
1
2
3
2
1
1
1
1
1
2
2
2
2
2
2
1
2
1
2
1
1
2
2
1
1
3
1
1
1
2
1
2
1
1
2
2
2
2
2
1
1
2
2
2
2
1
1
1
1
2
3
1
3
1
2
1
1
2
2
2
2
2
3
2
2
1
2
1
1
1
1
1
2
1
1
1
1
2
1
2
1
2
1
1
2
3
3
2
1
1
2
1
2
2
1
2
1
2
2
1
1
1
2
2
1
3
2
1
1
1
2
2
2
2
1
2
1
2
3
1
1
1
2
2
1
2
2
1
1
2
2
1
1
1
2
1
1
1
1
1
1
1
1
2
2
2
2
1
2
2
2
1
2
1
2
1
2
2
2
2
1
1
2
1
2
2
1
1
1
1
3
2
1
2
1
1
1
2
1
1
3
1
2
3
1
3
2
3
1
1
3
2
1
2
2
2
1
1
1
2
2
1
2
1
2
1
1
2
2
2
1
2
1
2
1
1
1
2
3
2
2
1
2
1
2
1
2
2
2
1
1
1
1
2
2
2
2
1
1
2
2
2
1
1
2
3
2
3
1
2
3
1
1
2
2
2
2
2
2
2
1
2
2
2
2
1
1
2
2
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
1
1
1
1
1
1
2
1
2
3
1
2
1
3
2
2
1
1
1
1
1
2
2
1
3
2
2
1
2
1
3
1
1
3
2
1
1
2
2
1
1
1
2
2
2
1
3
1
1
1
2
1
1
1
1
2
1
2
1
1
2
2
1
2
1
1
1
1
1
3
2
1
1
3
2
2
2
1
2
2
2
2
1
2
1
1
1
1
1
1
2
1
1
1
2
2
2
2
1
3
3
1
2
2
1
2
1
2
1
2
3
2
1
1
1
1
2
1
2
2
2
2
2
2
3
1
1
2
1
2
2
1
2
1
2
1
1
1
1
1
2
1
2
3
2
1
1
2
1
1
1
2
1
1
1
2
2
1
1
1
2
2
2
2
1
2
1
1
1
2
1
1
3
1
1
2
1
2
1
2
2
2
1
3
2
2
2
2
1
1
1
1
2
1
1
2
1
2
1
2
1
1
3
3
2
1
1
2
1
1
2
2
2
2
2
2
2
1
1
1
1
1
1
1
2
2
1
1
2
1
2
1
3
2
1
2
2
2
2
2
1
2
1
1
2
1
1
1
2
2
1
2
2
2
2
1
1
2
2
1
2
1
1
2
2
2
2
2
1
1
1
2
1
1
1
1
1
1
1
2
1
1
2
1
2
1
2
1
2
1
1
2
3
2
2
1
1
2
1
2
2
2
1
1
2
2
2
1
2
1
1
1
1
2
1
1
1
2
1
1
1
1
2
3
2
2
2
1
1
1
1
2
1
1
1
1
2
1
1
3
2
1
3
3
2
1
2
2
1
1
2
3
2
2
1
1
2
3
2
1
1
3
1
1
2
1
1
1
1
3
2
3
1
2
2
2
1
1
2
2
3
1
3
2
1
1
1
1
1
1
1
2
1
1
2
1
2
2
1
2
1
1
2
1
2
1
1
1
2
1
2
1
3
1
1
1
1
2
1
3
2
1
1
3
2
3
1
1
1
3
1
2
2
1
1
3
2
1
2
1
2
1
2
2
1
2
2
3
2
2
3
1
1
3
1
2
3
2
1
2
3
3
3
2
2
2
2
1
1
3
2
1
2
2
1
1
3
1
1
2
1
2
1
1
1
1
1
1
2
2
1
1
1
2
1
2
1
2
1
1
2
2
2
1
2
1
2
1
3
2
2
1
1
2
1
2
2
3
1
2
2
1
2
2
1
2
2
1
1
2
2
1
2
2
2
1
2
1
1
2
1
1
1
2
1
1
1
1
3
2
1
1
3
2
1
1
1
2
2
1
1
1
1
2
1
1
2
2
1
1
1
2
1
2
2
2
1
1
1
1
1
2
2
1
2
1
1
1
1
1
1
1
1
1
2
1
2
1
2
1
2
2
1
2
1
1
3
2
1
1
1
1
2
2
2
1
2
1
2
1
2
2
2
2
1
2
1
1
1
2
3
2
3
1
1
3
2
2
1
2
3
3
3
1
2
1
1
1
1
2
2
1
2
3
2
3
2
1
1
1
1
2
1
1
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
2
1
1
2
2
2
2
1
1
2
2
1
1
2
1
1
1
2
2
1
1
1
1
1
2
2
2
1
1
2
2
3
1
2
3
3
1
1
1
1
1
1
2
3
1
1
2
1
1
2
2
1
2
1
2
1
1
1
1
2
2
1
1
1
2
2
3
1
2
2
1
2
1
2
1
2
2
2
1
1
1
3
1
1
2
1
3
1
2
1
1
2
2
3
1
1
2
2
2
3
2
2
1
1
1
2
1
2
2
2
1
1
2
1
1
2
1
2
1
2
2
1
2
3
1
1
2
2
1
1
1
2
2
2
1
1
1
2
1
2
1
3
1
2
1
1
2
1
1
3
2
1
1
1
1
1
1
2
1
1
2
1
2
2
1
1
1
3
2
2
2
2
1
2
2
1
1
2
1
3
3
1
1
2
1
2
1
2
1
1
2
2
2
3
2
1
1
1
2
1
2
3
1
2
1
2
1
1
1
1
1
3
2
3
1
1
1
2
1
1
1
1
1
1
2
1
2
2
2
2
3
2
1
2
1
2
1
1
2
2
1
1
1
2
2
1
1
1
1
1
1
1
2
1
2
1
2
1
1
1
2
1
1
1
1
1
1
1
2
1
3
1
2
1
1
2
2
2
1
1
2
3
1
1
1
1
3
1
2
1
1
1
2
1
2
2
2
1
3
1
1
2
2
2
3
1
2
2
2
1
3
2
1
1
1
1
2
1
1
1
1
1
2
1
1
2
3
1
2
1
2
3
2
1
1
3
1
1
1
1
2
1
3
1
1
1
1
1
1
2
2
2
1
1
2
1
3
1
1
1
1
1
1
2
3
2
2
1
1
1
2
2
2
2
1
2
2
2
2
1
2
1
1
1
2
1
2
2
1
2
1
1
2
2
2
1
1
1
1
2
3
1
1
2
1
1
2
1
1
1
1
3
2
1
2
1
2
2
2
1
2
1
1
1
1
1
2
1
1
1
1
1
2
1
1
1
1
2
2
1
1
1
1
1
2
1
3
1
2
3
1
1
2
1
1
2
2
1
2
2
2
1
3
1
2
1
2
2
2
1
3
2
2
1
1
2
2
3
2
2
1
1
1
3
1
2
1
1
1
1
2
2
2
2
1
1
3
1
1
1
2
2
2
2
1
2
2
3
2
1
1
1
2
1
2
2
3
1
1
2
1
1
1
2
1
3
2
1
1
3
3
1
1
1
1
2
1
1
1
3
1
1
1
1
2
2
1
3
1
2
1
1
1
1
2
1
2
1
1
2
1
1
1
1
1
1
1
1
1
1
2
1
2
1
1
2
2
3
2
1
1
3
2
1
1
1
2
1
1
1
2
2
2
1
2
3
2
1
2
2
1
2
2
1
2
1
2
2
2
2
1
2
1
1
2
1
1
2
2
3
1
1
1
2
1
1
1
1
1
1
3
1
1
1
1
1
1
2
1
1
1
2
1
1
1
2
1
2
1
1
2
1
1
1
1
2
2
1
3
2
1
2
2
1
2
3
1
1
2
1
2
1
2
1
2
1
1
1
1
3
2
2
1
1
2
2
1
2
1
2
1
1
2
1
1
1
1
2
2
1
2
2
1
1
1
1
1
1
2
1
1
1
1
1
2
2
2
2
2
1
2
1
2
2
1
2
2
2
2
2
1
2
3
2
2
1
1
2
1
2
3
2
1
1
2
3
3
1
1
2
1
1
2
2
2
1
2
2
1
1
1
2
2
2
1
1
2
1
1
1
2
1
1
2
1
3
2
1
2
2
2
1
2
2
1
1
2
1
1
1
1
1
2
3
1
1
1
1
1
3
3
1
2
3
2
1
1
2
1
1
2
2
2
2
2
1
1
1
1
2
1
1
2
2
1
1
3
3
2
1
2
2
1
2
2
2
2
2
1
2
1
3
2
1
2
2
1
2
1
2
1
1
2
2
1
1
2
2
1
1
1
2
2
1
1
1
1
2
1
1
2
2
1
1
2
1
1
1
2
1
3
2
2
2
2
1
1
2
2
1
1
2
1
2
1
3
1
1
2
1
2
2
2
1
2
2
1
1
1
2
3
1
3
1
3
1
1
2
1
2
1
2
1
1
1
2
1
3
1
1
1
3
2
1
2
1
2
2
1
2
2
1
2
1
1
2
3
1
1
2
2
1
1
2
2
2
1
2
2
2
1
2
1
2
2
2
1
1
1
1
1
2
2
2
2
2
1
2
1
1
1
1
2
2
2
2
1
3
2
3
2
1
1
1
1
2
1
2
1
2
1
2
1
2
1
1
2
1
1
2
1
2
2
2
2
1
2
2
3
1
1
2
1
1
1
1
2
1
2
2
2
1
2
1
1
1
1
2
2
1
1
1
2
1
2
2
1
1
1
1
1
1
2
2
2
1
1
1
2
2
1
2
2
1
2
2
2
1
1
2
1
3
1
2
1
2
2
1
1
1
1
2
1
2
3
1
1
1
1
2
2
1
2
2
1
2
1
2
1
3
2
1
3
2
2
2
1
1
2
1
1
1
2
2
1
1
1
1
2
1
2
2
2
1
1
1
1
1
2
1
1
2
1
3
3
1
1
2
1
3
2
1
1
3
1
2
1
2
2
2
1
1
2
2
1
2
1
1
1
2
2
1
1
1
1
1
1
1
2
2
2
1
1
2
2
2
2
1
1
2
1
2
1
2
2
3
1
2
1
1
1
2
1
1
2
1
3
2
3
2
1
1
3
3
1
1
2
1
1
1
2
1
1
2
3
3
2
1
2
1
1
3
1
1
1
1
1
1
1
2
2
1
1
1
1
2
1
1
2
2
1
1
2
2
1
2
1
2
1
2
2
1
1
1
2
2
2
1
2
2
1
1
1
1
3
1
1
1
2
1
3
2
1
2
1
1
1
2
1
1
1
2
1
2
2
1
2
1
2
1
1
2
1
2
1
1
1
1
1
1
1
1
2
1
2
1
3
2
1
2
1
2
3
1
2
2
1
1
1
3
1
1
2
1
1
1
2
1
2
2
1
1
3
2
1
1
3
1
2
2
1
2
2
2
3
2
1
1
1
3
2
1
1
1
2
1
1
1
2
2
2
1
1
1
1
2
2
2
3
2
1
1
1
1
2
2
1
1
1
1
1
1
2
2
2
1
1
1
2
1
3
2
2
1
2
2
2
1
2
2
1
2
1
1
1
2
2
1
2
1
1
2
2
2
2
2
2
2
1
1
1
1
1
1
2
1
1
1
1
2
1
1
1
2
3
1
1
1
2
2
1
2
1
1
1
1
1
3
3
2
2
2
2
2
1
2
1
1
2
2
1
1
1
2
1
2
2
1
2
2
1
3
1
1
1
2
1
2
1
2
1
1
2
2
1
2
1
1
2
1
1
1
1
1
1
2
2
2
3
1
1
1
1
2
1
3
1
1
2
2
3
2
3
1
1
1
3
2
1
1
1
1
2
2
1
2
1
2
1
1
2
3
3
2
2
1
2
1
1
1
1
1
1
2
2
1
2
2
1
1
2
3
2
1
1
2
1
2
2
1
2
1
2
1
1
2
2
1
1
1
1
1
1
1
1
2
1
1
1
1
3
1
1
1
2
1
1
2
1
1
1
3
1
2
2
3
2
1
2
1
1
2
1
1
2
2
2
2
2
3
1
1
1
2
1
2
2
1
2
1
1
2
1
2
2
2
2
1
1
1
3
1
3
2
1
2
1
2
2
2
1
2
2
1
1
2
1
1
1
2
1
1
1
1
1
1
1
2
3
1
2
1
2
1
2
1
1
3
2
2
2
1
2
1
1
1
2
2
1
2
1
1
3
1
1
1
2
1
1
3
1
2
2
1
2
1
1
1
1
2
3
1
1
1
2
1
2
1
1
1
2
1
2
2
1
1
2
1
1
1
2
1
1
1
3
1
1
2
2
2
1
2
2
2
1
2
2
2
1
1
2
2
3
1
1
1
1
1
3
1
2
1
1
1
2
2
1
2
1
1
2
1
2
3
1
2
1
2
2
1
1
1
3
1
2
1
1
2
1
1
2
2
1
2
3
2
1
2
2
2
1
1
2
2
1
1
2
3
2
2
2
2
1
2
2
2
2
1
2
2
3
1
1
1
2
2
1
2
2
1
1
1
2
1
2
3
1
2
3
1
2
1
1
1
1
3
1
1
2
3
2
2
2
1
1
2
2
2
3
1
2
2
1
2
2
2
2
1
2
2
1
1
2
1
2
2
2
1
2
2
2
1
1
1
1
2
2
1
3
1
1
1
1
2
2
1
2
2
2
2
2
1
1
2
1
1
1
2
2
1
1
2
2
2
1
2
1
2
1
2
1
3
3
3
1
2
1
2
1
1
1
1
2
2
1
3
2
1
1
1
1
1
1
2
2
1
1
1
2
1
1
1
1
2
1
1
1
2
1
2
3
1
1
1
1
1
1
1
2
2
2
2
2
2
1
2
1
2
1
2
1
3
1
1
2
1
1
2
1
2
2
2
2
1
2
2
1
1
2
2
1
2
1
2
2
1
3
2
1
1
3
2
2
1
2
2
2
3
3
1
3
2
2
2
1
1
1
2
1
1
3
2
2
3
1
1
1
1
2
2
1
2
1
1
2
1
2
1
1
2
1
2
2
1
2
2
1
2
2
2
1
1
1
1
1
1
2
1
1
1
1
1
2
1
2
1
2
1
2
1
2
2
1
2
1
1
1
1
2
2
3
2
1
1
1
2
1
2
1
1
1
2
1
1
1
1
3
1
1
1
1
3
2
1
2
2
1
1
1
1
2
1
1
2
2
2
2
1
3
1
1
2
2
2
1
1
2
1
1
2
2
3
1
1
2
1
2
1
1
2
2
2
1
2
2
1
1
1
2
1
2
2
1
3
2
1
2
2
3
3
1
2
1
2
2
1
1
2
3
3
1
1
2
2
2
2
2
2
2
1
1
1
1
1
2
2
1
2
2
2
1
1
1
3
1
1
2
2
1
1
1
2
1
2
3
3
1
2
1
2
2
1
2
3
1
1
3
2
2
2
1
1
3
1
1
2
1
1
2
1
1
2
1
1
2
1
2
2
2
1
1
2
2
2
1
1
1
2
1
1
2
2
1
2
1
1
3
1
1
1
2
1
3
1
3
3
1
1
1
2
1
1
2
2
1
1
1
1
1
1
1
3
3
2
2
2
1
2
1
1
2
1
2
2
1
2
2
2
2
1
2
1
3
2
2
2
1
2
2
2
1
2
2
2
1
2
3
2
3
2
3
1
2
2
1
2
1
2
1
2
1
1
2
2
1
2
2
2
1
1
2
1
2
1
1
1
3
1
2
1
1
1
1
2
2
1
2
1
1
2
1
2
1
2
1
1
1
2
2
1
1
1
2
3
1
1
1
1
1
1
2
2
2
3
1
1
2
3
2
1
1
2
1
1
1
1
1
1
2
1
1
1
1
1
1
2
3
1
1
1
2
2
1
1
1
2
1
2
2
1
1
1
1
2
3
1
1
2
2
1
2
3
2
2
1
1
2
1
2
1
1
2
2
2
2
1
2
1
2
1
2
2
1
1
2
2
1
1
2
3
1
1
1
1
2
1
1
2
2
2
1
1
3
1
1
1
1
1
1
1
1
2
2
1
2
2
1
1
1
1
1
1
1
1
1
1
2
1
2
2
1
2
1
2
1
2
2
1
1
1
1
1
1
1
1
2
2
3
1
2
1
2
1
1
1
1
1
1
2
1
1
2
2
1
2
2
1
1
3
1
1
2
2
2
3
1
1
2
1
2
1
1
1
1
3
2
3
2
1
1
2
1
1
1
1
1
1
2
2
1
1
1
2
1
1
1
2
2
1
2
1
1
2
1
1
2
1
1
1
1
1
1
2
2
1
2
1
1
2
1
2
1
2
3
1
1
2
1
1
2
1
1
3
2
2
2
1
2
1
1
2
1
1
2
1
3
2
1
3
1
1
2
1
1
2
1
2
1
2
2
2
1
2
1
3
1
2
2
1
2
1
3
1
1
2
2
1
2
1
2
1
2
2
2
2
1
2
2
1
2
2
1
2
1
2
2
3
2
3
1
2
1
2
1
2
2
1
1
2
1
1
2
1
2
2
2
1
2
1
1
1
1
1
2
1
3
1
1
1
2
1
1
1
3
1
1
1
1
1
3
3
2
1
1
2
1
1
1
1
1
1
2
2
2
2
2
1
1
1
2
2
1
1
1
1
1
1
1
1
2
2
1
1
2
2
2
2
2
1
2
1
2
1
1
2
2
1
1
1
1
1
1
1
2
2
2
3
2
2
1
1
1
2
1
2
1
2
2
1
2
3
1
1
1
1
1
1
3
2
1
1
1
1
2
1
1
2
1
1
1
1
2
3
2
1
1
2
2
1
2
1
3
2
1
2
1
1
1
2
1
1
2
2
1
2
3
3
1
3
2
1
2
2
1
1
2
1
2
1
2
1
3
2
1
2
2
1
1
2
1
2
1
1
1
1
1
2
2
1
2
3
1
1
2
1
1
1
1
2
2
1
2
2
1
1
1
1
2
3
1
3
2
2
1
2
1
1
2
3
2
1
2
2
2
2
3
3
1
2
2
1
1
1
2
1
1
2
1
3
1
2
1
2
1
1
1
2
1
2
1
2
1
2
1
2
2
1
2
1
1
1
1
1
2
2
1
2
1
1
2
1
1
1
2
2
2
1
1
2
1
2
1
2
1
1
2
1
2
2
1
2
2
2
1
1
2
2
1
1
3
2
1
1
1
1
2
1
1
1
2
2
2
1
1
2
1
1
2
1
2
2
2
2
2
2
1
2
1
1
3
1
1
2
2
2
1
2
1
1
1
2
3
1
1
1
1
1
2
2
1
2
2
1
1
1
1
2
2
2
3
2
2
1
2
2
3
3
2
2
1
2
1
2
2
2
2
2
1
1
2
1
1
2
2
1
2
1
2
1
1
1
2
1
1
2
1
1
1
2
1
2
2
1
1
3
2
2
1
1
2
1
2
1
2
1
2
1
1
2
2
1
2
1
1
2
1
1
1
1
1
2
2
2
2
1
1
1
3
1
1
2
3
1
1
1
1
2
1
2
2
2
2
1
2
1
1
1
2
2
1
1
1
3
2
2
2
1
1
1
2
2
3
1
2
1
2
1
2
2
1
1
1
1
1
3
1
1
1
2
1
1
1
2
1
3
1
2
3
1
1
1
1
3
2
2
2
1
1
2
2
2
2
2
2
1
2
1
1
1
1
2
1
1
1
2
2
1
1
1
1
2
1
1
1
2
2
3
2
2
1
1
1
2
2
1
2
1
3
1
1
1
2
2
2
2
2
1
3
2
2
1
1
2
2
1
1
1
2
3
2
2
1
2
2
1
1
2
1
1
1
2
1
2
2
2
1
1
2
1
2
3
2
1
1
1
1
1
2
3
1
1
3
2
1
2
2
2
1
1
1
1
3
1
1
1
2
2
2
1
1
1
1
1
1
2
2
1
1
1
1
1
3
2
1
1
2
2
1
2
1
1
2
2
2
2
2
1
3
1
1
2
1
3
1
2
1
1
2
1
1
2
1
3
2
1
3
1
2
1
1
2
1
1
2
1
2
2
1
2
1
1
2
1
1
2
2
1
2
1
1
2
1
1
3
2
1
1
2
2
2
2
3
1
2
3
2
2
2
1
1
1
1
2
1
1
1
1
1
2
1
1
3
1
2
2
1
1
2
1
2
2
2
2
2
1
1
1
2
1
1
1
1
1
1
2
1
2
1
2
1
2
2
1
1
2
2
2
1
1
3
2
1
2
1
1
1
2
1
3
3
1
1
1
2
1
1
2
2
1
1
1
2
2
1
1
2
2
1
1
1
2
1
1
1
2
3
2
1
2
1
1
1
2
1
1
1
2
2
2
2
2
1
2
1
2
1
1
1
2
1
2
3
1
2
1
3
2
2
2
1
2
1
1
1
1
1
2
1
1
1
1
2
1
1
2
1
2
2
1
1
2
1
1
2
1
1
2
1
1
2
3
1
1
1
1
2
2
2
2
1
1
1
1
2
1
1
1
1
2
2
1
1
1
1
1
2
1
2
2
3
2
1
2
3
1
1
1
1
2
1
1
2
2
1
2
1
1
2
1
2
1
2
1
1
2
1
1
1
1
1
3
2
1
2
1
1
2
2
1
1
1
2
2
2
1
2
2
1
1
1
1
2
1
1
1
2
2
1
1
1
1
3
2
1
1
3
2
1
2
2
1
1
1
1
2
1
2
2
1
1
2
3
2
2
1
1
2
1
2
3
2
2
2
1
1
2
2
2
1
1
1
3
1
1
1
1
1
1
2
1
3
1
2
3
1
2
3
1
2
1
1
1
1
1
2
2
2
2
2
1
2
1
3
1
2
2
2
2
3
1
2
2
3
1
1
2
3
1
2
2
2
1
1
1
2
1
1
2
1
2
2
1
2
1
1
1
2
1
2
2
2
1
1
1
1
1
1
2
2
2
1
2
3
2
2
3
1
2
1
3
2
1
1
1
1
2
1
3
1
1
1
2
3
2
1
2
1
2
2
2
2
2
2
2
1
1
1
1
2
1
1
2
1
1
3
1
2
3
1
2
1
1
1
1
1
2
2
2
2
2
1
1
1
3
1
2
2
2
2
1
1
1
2
2
1
1
1
3
2
1
1
2
2
2
1
1
1
1
1
1
1
2
1
1
1
1
2
2
1
1
1
3
2
2
2
2
2
3
1
1
2
1
1
3
2
2
2
1
2
1
2
3
1
1
2
1
3
1
1
2
2
2
2
1
2
1
1
1
3
1
2
1
2
1
2
1
2
1
1
1
1
1
3
1
1
1
2
2
2
1
1
1
2
1
1
1
3
2
2
2
1
1
1
2
2
2
2
1
2
1
1
1
1
1
1
1
1
3
1
1
1
1
2
1
2
1
1
2
1
1
2
1
2
1
1
2
2
1
1
3
2
2
2
1
1
1
2
1
2
1
1
2
1
1
2
1
3
2
1
1
2
1
2
1
1
1
1
3
1
1
1
2
2
2
1
1
1
2
3
2
1
2
2
1
1
2
1
3
3
1
1
2
1
1
3
1
1
2
1
1
1
1
1
1
2
1
1
2
2
2
1
1
1
2
1
1
1
1
2
1
2
1
2
1
2
2
1
1
2
1
2
2
2
2
2
2
2
1
2
1
1
2
2
1
1
2
1
2
2
1
1
2
2
3
1
1
2
1
1
2
1
2
2
3
1
1
1
2
3
1
2
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
1
1
1
2
1
2
2
1
1
1
1
1
1
1
2
1
2
2
2
1
1
2
2
3
2
1
1
2
2
1
3
2
2
1
1
1
1
1
3
1
1
2
2
3
2
2
2
2
1
1
1
2
3
1
2
1
1
1
1
1
1
2
1
1
2
2
1
3
1
1
1
2
1
2
2
2
1
1
1
1
3
2
1
3
2
1
2
1
2
1
1
1
2
1
1
1
1
1
1
3
3
1
1
2
1
1
2
1
1
1
1
1
1
2
1
1
1
2
1
1
2
1
1
2
2
1
2
2
2
1
2
2
2
2
1
2
1
2
3
3
1
3
2
2
2
1
2
1
1
2
1
1
2
2
2
2
1
2
2
1
1
1
3
1
1
2
2
1
1
1
1
1
1
1
2
2
3
1
1
1
1
1
1
1
1
3
2
1
3
1
1
1
1
2
2
2
1
1
1
1
2
1
1
1
1
1
2
1
1
1
1
1
2
2
2
1
2
1
2
1
1
1
2
1
1
2
1
1
2
1
3
2
2
2
2
1
1
1
2
2
2
2
1
2
1
1
2
2
2
3
2
1
1
1
2
1
1
2
1
1
1
1
1
2
1
1
1
1
2
2
1
3
1
1
1
1
1
1
3
1
2
1
2
2
1
1
2
1
2
3
2
1
3
1
2
2
1
3
1
1
2
1
2
1
2
1
2
1
2
3
1
1
2
1
1
3
3
2
2
2
2
2
1
1
1
2
2
2
2
2
1
1
2
2
2
1
2
2
2
2
1
2
3
2
2
1
1
2
1
1
1
3
2
3
1
1
1
2
2
1
2
2
1
1
2
1
1
1
2
2
2
2
1
1
2
3
1
1
1
2
2
2
1
3
1
1
1
2
2
1
2
1
3
2
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
2
1
1
3
1
1
1
1
2
3
3
1
3
2
1
1
1
2
1
1
2
1
2
2
1
2
1
2
2
2
1
1
2
1
1
2
1
1
2
1
1
2
1
1
3
1
1
2
1
1
1
1
2
1
2
2
1
2
1
1
2
1
2
2
1
2
1
1
1
1
1
2
2
1
2
1
2
3
2
2
1
3
2
2
1
3
1
1
1
1
2
1
2
1
2
2
1
2
1
2
2
1
2
2
2
1
2
3
1
3
1
1
2
2
3
1
2
1
1
1
1
2
2
1
2
2
2
2
2
1
1
2
3
2
3
2
2
1
1
3
1
1
1
2
3
2
1
2
3
2
2
3
2
3
2
3
2
1
1
2
2
2
2
1
2
2
1
1
3
2
1
2
2
2
1
2
1
2
3
2
2
1
2
2
1
3
2
1
2
2
2
1
1
2
1
1
1
2
1
2
1
1
1
2
1
2
1
1
2
1
2
1
1
1
2
1
1
2
1
2
2
1
3
2
1
1
1
1
1
2
2
1
1
1
2
1
1
3
3
2
1
2
2
1
2
3
1
2
1
1
1
1
1
2
2
1
3
3
1
1
1
2
2
2
1
3
2
1
2
1
1
1
2
1
1
1
2
3
3
2
1
1
1
1
2
1
1
3
3
2
3
2
3
2
1
1
1
2
2
1
2
1
1
3
1
2
3
1
2
2
2
1
1
1
2
2
1
1
1
2
1
2
1
3
3
1
1
3
2
2
2
2
1
2
3
2
1
1
1
2
2
1
2
2
2
2
1
2
2
1
1
1
2
1
1
1
2
1
2
1
1
1
2
1
2
1
1
2
1
1
2
2
1
1
3
2
2
1
2
2
1
2
3
1
1
2
3
2
2
2
2
1
1
2
1
1
1
1
1
2
1
2
1
2
1
2
2
1
3
2
1
2
2
1
1
1
2
2
2
2
1
1
2
1
1
1
1
3
2
2
1
1
3
1
1
2
1
1
2
1
1
2
1
2
1
1
1
2
1
1
1
2
1
2
1
3
1
2
1
3
3
2
1
1
1
1
1
1
1
1
1
1
1
3
1
1
2
1
1
2
1
1
1
2
3
2
1
1
1
1
1
1
2
1
1
2
1
2
1
1
2
2
2
1
2
1
1
2
2
1
1
2
1
1
1
3
1
1
1
1
2
2
1
2
1
3
1
1
2
2
2
2
2
1
1
1
2
2
2
2
3
2
1
2
1
2
1
2
2
1
3
1
1
1
1
1
2
1
2
1
2
3
2
3
1
3
2
1
1
2
1
2
2
1
1
2
1
1
2
2
1
2
1
1
3
1
3
1
1
1
2
3
2
2
1
1
2
2
1
1
3
1
1
1
1
2
1
2
2
1
1
1
1
2
2
2
3
2
1
1
1
1
1
2
1
2
1
2
2
1
2
1
2
1
1
1
1
1
2
1
1
1
1
1
2
1
1
2
1
2
1
2
1
3
3
1
2
1
1
1
1
1
1
1
2
3
1
2
1
2
1
2
1
1
1
2
2
1
3
1
2
3
2
2
1
2
3
1
1
2
1
1
1
2
1
2
1
1
1
2
1
1
2
2
1
1
3
1
3
2
2
2
2
2
1
2
1
1
1
2
2
2
1
1
1
2
3
1
1
2
1
1
2
2
2
1
1
1
1
3
1
1
1
1
1
1
1
2
1
3
2
1
1
2
2
2
1
2
1
2
2
3
1
1
1
1
1
3
1
1
1
1
1
1
2
2
2
2
2
3
1
3
2
1
1
2
3
2
1
1
1
2
2
2
1
2
1
1
1
1
3
1
2
2
1
3
2
1
3
2
1
1
1
1
2
2
1
2
2
2
1
3
1
2
1
2
1
2
2
1
1
1
3
2
1
1
1
1
2
1
2
2
1
2
2
1
1
1
1
2
2
1
3
1
1
1
1
1
2
2
2
1
1
3
2
1
1
1
1
3
2
2
2
1
2
1
1
2
2
1
2
1
1
1
2
1
1
1
1
2
2
1
2
1
2
1
1
1
2
1
1
2
1
2
1
1
2
2
1
1
1
2
1
2
3
1
2
1
1
2
1
1
1
2
2
2
1
1
2
2
1
1
1
1
2
1
2
3
1
2
1
2
1
1
3
1
1
3
1
1
2
2
2
2
1
1
3
1
2
2
1
2
2
1
2
1
1
2
1
2
2
1
1
2
1
1
1
1
2
2
3
1
1
2
2
2
1
2
3
1
1
1
1
1
2
3
1
2
3
1
2
1
1
1
1
2
1
1
2
3
3
1
1
1
1
1
2
2
2
2
1
3
1
1
1
3
2
2
2
1
3
3
2
2
2
1
2
3
2
1
2
2
2
1
1
2
2
2
2
1
2
1
2
3
1
1
3
2
1
1
2
1
2
2
1
2
2
1
1
2
2
2
2
1
1
2
1
2
2
1
1
1
3
3
2
2
1
1
1
2
2
1
2
2
2
2
1
2
1
2
1
1
1
1
2
1
1
1
1
1
2
2
1
1
2
1
2
1
1
3
2
1
1
2
2
1
1
1
2
2
2
2
2
1
2
1
2
1
1
1
1
1
2
2
1
1
2
3
1
2
1
1
1
2
2
1
1
2
1
2
2
1
2
1
1
1
1
3
2
1
2
1
1
1
1
1
2
2
1
1
2
2
2
1
1
2
2
1
2
2
1
1
2
1
1
1
1
1
1
2
1
1
2
1
1
2
2
1
1
2
1
2
2
1
2
2
2
1
3
1
2
1
1
2
2
3
1
1
1
1
1
1
2
2
1
1
1
2
2
2
2
1
1
1
2
2
2
2
1
1
1
1
1
1
1
2
2
3
3
1
1
1
1
1
1
3
1
1
3
1
2
2
2
2
2
1
2
1
1
1
1
2
2
1
2
3
1
1
2
2
2
1
1
2
1
2
3
2
1
3
2
2
1
2
1
1
3
1
2
3
1
2
2
1
2
1
2
1
1
2
1
2
2
1
2
2
2
1
1
2
2
1
1
3
1
3
3
2
1
2
2
2
2
1
3
3
1
1
1
2
2
1
2
1
2
2
2
2
2
2
1
2
2
1
1
1
1
1
2
1
1
2
2
2
1
2
1
1
1
2
1
1
1
1
1
2
3
2
1
1
1
3
2
2
1
2
1
2
2
2
1
1
1
2
2
2
1
2
1
1
2
1
2
1
2
2
2
1
1
2
2
1
1
1
2
2
1
2
1
2
1
2
2
3
2
3
1
2
2
2
1
2
2
2
1
3
3
1
1
1
1
1
3
3
1
2
2
1
2
3
1
1
1
1
1
2
1
1
2
3
2
3
1
1
1
2
1
2
1
2
3
1
2
2
1
1
1
1
3
1
1
1
2
1
2
1
1
2
1
1
1
1
1
1
2
2
2
1
1
3
1
1
2
2
1
1
1
2
1
2
1
3
1
1
1
1
2
1
1
2
2
2
1
1
2
3
2
1
3
2
3
2
2
2
1
1
1
1
1
1
1
1
2
2
1
3
2
3
1
1
1
2
2
1
1
1
2
1
1
1
1
1
3
1
1
2
3
1
3
2
2
3
2
1
1
2
2
1
2
2
3
1
2
1
1
2
2
1
2
2
2
1
2
1
2
2
3
2
1
1
2
1
1
1
3
2
1
2
1
1
1
1
3
2
1
1
1
2
2
2
1
2
1
1
2
2
1
2
1
1
2
2
1
1
2
1
2
1
1
2
1
2
3
2
1
2
2
1
2
2
2
2
2
1
1
2
3
3
1
1
1
2
1
2
1
3
2
1
2
1
1
1
1
1
2
3
2
1
1
1
2
1
1
2
3
1
1
1
2
2
1
2
2
2
2
1
2
3
2
2
1
2
1
2
1
2
1
1
1
2
2
1
1
2
1
2
1
1
1
2
2
2
1
1
1
2
1
2
2
1
1
1
1
1
1
2
1
3
2
2
1
1
1
2
2
2
1
2
1
1
3
1
2
1
2
2
2
2
1
1
1
2
1
1
1
3
1
2
1
2
2
1
2
1
1
2
2
1
3
2
1
2
1
1
2
2
1
1
2
1
1
1
2
2
2
1
1
3
2
2
2
1
1
3
3
2
2
1
1
1
1
2
1
1
1
2
1
2
1
2
1
1
3
1
1
1
1
1
1
1
2
3
2
1
1
2
2
1
1
1
1
1
1
2
1
3
2
2
2
2
1
2
1
1
1
1
1
1
2
1
2
1
2
1
3
1
1
2
2
1
1
1
1
2
2
1
1
2
1
1
1
2
3
2
3
1
1
2
1
2
2
1
2
1
1
2
1
1
2
3
3
2
1
2
2
2
1
1
1
2
1
1
1
1
2
1
1
2
2
3
2
1
1
1
1
2
1
1
1
2
2
1
2
2
2
3
2
1
1
2
2
2
2
1
1
2
2
2
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
2
1
1
1
1
1
2
1
1
1
2
2
2
2
1
2
2
2
2
1
2
3
2
1
2
2
1
3
1
3
3
3
1
1
3
1
1
1
1
1
2
1
1
2
1
2
1
2
1
1
2
1
2
2
1
3
1
1
1
2
3
1
1
1
2
1
1
1
2
2
2
1
2
2
2
1
1
1
2
1
2
2
1
2
3
1
2
1
1
2
1
1
1
1
1
1
1
1
1
1
2
2
1
1
2
1
1
2
1
2
1
2
2
2
2
1
1
1
1
2
1
3
2
1
1
2
1
1
2
1
2
1
2
2
1
1
3
1
3
1
2
2
1
1
1
1
1
1
2
2
1
1
1
2
1
1
2
1
2
2
1
1
1
2
1
1
2
1
2
2
1
1
1
2
1
1
2
1
2
1
2
1
2
2
2
1
2
1
1
2
3
1
2
1
2
1
1
1
1
1
2
2
1
2
2
1
1
2
2
1
2
1
2
1
1
1
2
1
1
1
1
3
1
1
2
1
1
1
1
2
1
2
1
2
2
2
2
1
2
3
2
1
2
2
1
1
3
2
1
1
1
1
2
3
1
1
1
1
3
1
2
1
1
2
1
2
3
1
1
2
1
1
1
3
2
2
1
2
2
1
1
1
1
1
1
1
1
2
1
2
2
1
2
1
1
3
2
1
2
1
1
2
2
2
1
1
1
2
2
2
1
2
1
2
2
2
2
2
1
1
1
2
1
2
2
1
2
1
2
1
1
2
1
2
3
2
1
1
1
1
2
1
2
2
2
2
2
1
1
2
2
1
1
1
2
1
2
1
1
1
2
2
2
2
1
2
1
1
1
3
1
2
1
1
1
1
2
2
1
2
1
2
2
1
1
1
2
1
1
1
2
2
1
2
1
1
1
1
1
1
2
2
2
2
1
1
1
1
2
1
2
1
1
2
1
2
1
1
2
1
2
1
1
2
1
2
2
2
1
1
2
3
1
3
2
2
3
1
2
1
2
1
1
2
1
1
3
1
1
1
2
2
2
1
1
1
3
1
1
2
1
2
1
2
1
1
2
2
1
1
1
2
2
2
1
1
2
1
2
3
3
2
2
1
2
1
1
2
1
1
2
2
3
2
2
1
2
1
2
1
2
2
1
1
2
1
1
1
1
3
2
1
2
1
1
1
3
2
1
1
1
1
1
2
1
1
3
3
2
1
1
1
2
1
1
1
1
3
2
1
1
2
1
2
1
1
3
2
1
1
2
1
1
2
2
2
1
1
3
2
2
2
1
2
1
2
1
2
2
2
2
2
1
3
1
1
2
1
2
2
2
2
1
1
2
2
2
2
2
1
1
2
1
3
1
1
2
1
1
1
2
2
3
1
2
3
2
1
1
1
2
1
1
1
1
1
2
1
2
1
2
1
2
1
1
2
3
3
2
1
1
1
1
2
1
1
1
1
1
1
3
1
2
1
2
1
2
1
1
1
1
1
1
1
2
1
1
1
2
1
2
2
1
2
1
1
1
1
1
2
1
1
1
1
3
2
2
3
1
2
2
1
2
1
2
1
2
1
1
1
1
1
2
1
1
1
1
1
2
1
1
2
1
1
1
2
1
Your Output
3
1
2
2
2
1
2
1
2
2
1
1
2
1
1
2
2
1
2
2
1
1
1
3
3
2
2
3
1
2
1
1
1
1
2
2
2
2
2
2
2
1
2
1
1
2
1
2
2
1
1
1
1
2
2
2
1
2
1
2
1
2
1
1
2
1
2
2
1
2
2
1
3
3
2
2
1
2
1
3
1
2
2
1
2
2
1
2
1
1
2
2
2
1
2
1
2
1
2
3
2
1
1
1
1
3
2
1
1
1
2
1
1
1
2
2
2
2
1
2
1
2
1
2
2
2
2
2
1
1
1
2
1
2
3
2
2
2
1
2
2
2
2
1
3
1
2
1
1
2
2
1
1
2
2
3
3
2
3
1
1
1
1
2
1
2
1
1
1
3
1
1
2
3
2
1
2
1
1
1
2
1
1
1
2
1
2
1
3
1
2
1
2
1
3
2
1
2
2
2
2
1
1
1
1
2
2
2
2
2
1
1
1
1
1
2
1
2
2
2
3
2
1
1
1
1
2
3
2
3
1
2
2
1
2
2
2
3
1
1
2
2
1
2
2
2
1
1
3
2
2
1
1
2
3
1
2
1
2
1
2
1
2
3
1
2
2
2
1
2
2
1
3
2
1
1
2
2
2
1
2
1
1
1
3
1
2
1
2
2
1
1
1
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
3
1
1
1
2
1
2
2
2
2
1
1
1
2
2
1
1
2
2
2
1
1
2
1
2
2
2
1
2
2
1
1
1
1
1
1
2
1
2
2
2
2
1
1
2
2
1
2
1
3
1
2
2
2
1
2
2
2
1
2
2
1
2
2
1
1
2
1
1
2
2
1
1
2
2
2
2
2
2
2
2
3
2
2
1
1
1
3
2
2
2
3
2
2
1
2
2
2
1
3
2
3
2
1
2
1
1
2
3
2
1
2
3
2
2
2
1
1
2
2
3
1
2
2
1
1
2
3
2
2
1
1
1
2
2
1
2
2
2
1
2
3
1
2
1
2
2
3
2
1
2
2
2
1
1
2
3
2
2
1
1
1
1
2
3
1
1
2
2
2
1
2
2
3
2
2
2
2
1
1
1
2
2
2
3
2
1
2
1
1
2
2
1
2
2
2
2
2
2
1
2
1
1
1
1
1
1
1
2
2
2
1
1
2
1
2
2
1
1
2
2
1
1
1
2
1
2
2
2
1
2
2
2
1
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
2
2
2
2
2
2
2
1
2
1
3
1
2
2
1
3
3
1
1
1
2
1
1
3
2
2
3
1
1
2
1
1
3
1
2
1
1
2
2
1
2
1
1
2
2
1
2
2
1
1
3
2
1
3
1
2
1
1
2
2
2
1
3
2
1
1
2
3
2
1
1
2
1
1
2
1
2
1
2
1
3
1
2
1
1
1
1
2
1
2
3
2
1
1
2
2
2
2
2
2
2
1
1
2
2
1
1
1
3
1
1
3
1
3
2
1
1
2
2
1
3
3
1
2
1
2
2
1
3
3
1
2
1
1
1
2
3
1
2
2
2
1
1
1
2
2
1
1
1
1
1
1
2
2
1
2
1
2
2
2
1
2
1
1
1
1
2
2
1
1
2
2
1
2
2
2
2
2
1
2
1
1
1
1
2
3
2
2
2
1
1
1
1
1
1
1
1
2
2
1
2
2
2
1
1
1
3
2
1
3
1
1
1
1
1
3
1
1
1
1
1
1
2
2
1
2
2
2
2
2
2
2
1
2
3
1
2
2
2
2
2
1
1
1
1
1
1
2
1
2
1
2
1
1
2
2
2
1
2
2
1
1
1
1
2
2
2
1
2
1
2
2
2
2
2
2
2
2
2
2
2
1
2
1
1
1
1
2
1
1
1
2
2
2
1
2
1
2
2
1
1
2
3
3
1
1
2
2
2
1
2
1
1
2
2
2
1
3
2
2
1
1
2
2
1
3
1
2
2
2
2
2
1
2
1
2
2
3
2
2
1
2
3
2
1
2
1
2
2
1
2
2
1
2
2
1
1
1
2
2
1
2
1
2
2
2
1
1
2
1
1
1
1
2
1
2
1
3
1
1
2
1
1
2
1
2
2
1
2
3
1
2
1
3
2
1
1
2
1
1
1
2
1
1
2
2
2
2
1
3
3
2
3
1
2
2
2
1
3
2
1
2
2
2
2
1
2
1
1
3
1
1
2
1
1
1
2
3
1
1
2
3
2
2
2
2
2
1
1
2
2
2
2
2
1
1
2
1
1
2
3
2
1
2
1
1
1
2
1
3
2
2
2
2
2
1
2
3
1
2
1
2
1
2
1
2
2
2
2
1
1
1
1
2
2
2
2
1
1
2
1
2
1
2
2
2
2
2
3
1
1
2
2
2
3
2
2
2
2
1
3
2
1
2
2
2
2
2
2
2
1
2
2
1
1
2
2
1
2
2
2
1
1
3
2
2
2
3
2
1
2
1
2
2
1
1
1
1
1
2
1
1
1
1
1
2
2
2
2
3
1
1
2
1
1
1
1
1
1
2
1
2
2
2
2
2
3
2
2
1
2
2
1
1
3
2
1
2
2
3
1
2
2
1
1
3
2
2
2
1
1
1
1
2
1
2
2
1
1
2
2
1
2
2
2
1
2
1
2
2
1
3
2
1
2
1
1
1
1
1
2
3
1
1
1
2
3
1
2
2
1
2
1
1
2
2
1
1
1
2
2
2
1
1
1
1
1
2
2
1
2
2
3
2
1
1
2
3
2
3
3
2
1
2
1
1
2
1
2
2
1
2
1
1
2
1
1
2
1
2
2
1
1
2
3
2
2
2
2
2
1
1
1
3
2
1
1
1
2
1
2
1
2
2
2
1
2
3
1
1
1
1
2
2
1
2
1
1
1
1
2
1
1
2
3
1
3
2
2
2
1
2
2
1
2
2
2
2
1
2
2
2
2
2
1
3
3
2
1
1
2
1
1
2
1
1
1
1
1
1
2
2
1
2
1
2
1
2
2
2
1
2
2
2
2
2
2
1
1
1
2
2
1
3
3
1
3
1
2
2
2
2
2
2
1
2
1
3
2
2
1
3
1
1
2
2
2
2
2
1
2
2
2
1
2
2
1
1
1
1
1
2
1
1
2
1
1
2
3
3
1
3
2
2
2
2
3
1
2
2
3
1
3
2
1
3
1
1
2
2
2
1
2
1
1
2
2
1
2
2
2
2
2
1
2
3
1
1
1
1
3
1
1
2
3
1
2
2
3
1
1
2
1
1
2
2
2
2
1
3
2
1
1
2
2
1
2
2
1
2
1
1
1
1
2
2
1
1
1
2
2
1
2
2
1
1
2
2
1
2
2
2
1
2
3
2
1
1
1
2
2
1
2
1
2
2
1
1
1
2
2
1
1
1
2
2
2
1
1
1
2
2
1
1
2
2
1
2
2
2
2
2
3
1
2
1
2
2
1
1
1
1
3
1
3
2
1
2
1
2
2
1
1
2
2
2
2
1
2
1
2
2
1
2
3
1
2
3
1
1
1
1
2
3
1
2
1
1
2
1
1
2
2
1
2
3
2
1
1
3
1
1
1
1
2
1
2
2
2
3
1
1
1
2
1
1
1
1
1
1
2
3
1
2
1
1
1
2
1
2
1
3
2
2
1
2
1
2
2
1
2
2
1
1
1
1
1
2
1
3
1
2
2
2
2
1
2
2
2
1
3
3
2
1
1
2
1
1
1
1
1
2
1
1
1
3
1
1
2
1
1
2
1
2
1
2
1
2
1
1
1
2
2
2
2
2
1
3
2
2
1
2
1
3
1
3
1
1
2
2
1
1
2
2
2
2
2
1
2
2
3
1
2
1
3
1
1
2
1
1
1
1
1
1
1
1
2
2
1
2
2
2
2
1
2
3
1
2
1
2
2
1
1
1
1
1
1
2
2
2
1
3
2
1
1
1
2
1
2
2
2
1
2
1
2
1
2
2
1
2
1
1
2
2
2
2
3
2
1
1
1
2
1
2
1
2
2
1
2
2
3
2
1
2
1
2
1
1
2
2
1
2
1
2
1
2
1
1
2
3
3
1
1
2
2
2
2
2
1
3
1
1
1
1
2
3
2
1
1
1
1
2
2
2
2
2
2
2
1
2
1
2
1
1
2
2
2
1
3
1
1
2
2
1
2
1
1
2
2
2
2
2
1
1
2
2
2
2
1
1
1
1
2
3
1
3
1
2
1
1
2
2
2
2
2
3
2
2
1
2
1
1
1
1
1
2
1
1
1
1
2
1
2
1
2
1
1
2
3
3
2
1
1
2
1
2
2
2
2
1
2
2
1
1
1
2
2
1
3
2
1
1
1
2
2
2
2
2
2
1
2
3
1
1
2
2
2
1
2
2
1
1
2
2
1
1
1
2
1
1
1
1
1
2
1
1
2
2
2
2
1
2
2
2
1
2
2
2
1
2
2
2
2
1
1
2
2
2
2
1
1
1
2
3
2
1
2
1
1
1
2
1
1
3
1
2
3
1
3
2
3
2
1
3
2
1
2
2
2
1
1
2
2
2
1
2
2
2
1
2
2
2
2
2
2
2
2
1
1
1
2
3
2
2
1
2
1
2
1
2
2
2
2
1
1
1
2
2
2
2
1
1
2
2
2
1
1
2
3
2
3
1
2
3
1
1
2
2
2
2
2
2
2
1
2
2
2
2
1
1
2
2
2
1
1
2
2
2
2
2
1
2
2
1
2
2
1
1
1
1
1
2
1
2
1
2
3
1
2
2
3
2
2
1
1
1
1
1
2
2
1
3
2
2
1
2
1
3
1
1
3
2
1
1
2
2
1
1
1
2
2
2
1
3
1
1
2
2
1
1
1
1
2
2
2
2
1
2
2
2
2
1
2
2
1
2
3
2
1
1
3
2
2
2
1
2
2
2
2
2
2
1
1
1
2
1
2
2
1
1
1
2
2
2
2
1
3
3
1
2
2
1
2
1
2
1
2
3
2
1
1
1
1
2
1
2
2
2
2
2
2
3
1
1
2
1
2
2
1
2
1
2
1
1
2
1
1
2
1
2
3
2
1
2
2
1
1
1
2
1
1
1
2
2
1
1
1
2
2
2
2
1
2
1
1
1
2
1
1
3
1
1
2
1
2
1
2
2
2
2
3
2
2
2
2
1
1
2
1
2
1
1
2
1
2
1
2
1
1
3
3
2
1
1
2
1
1
2
2
2
2
2
2
2
1
1
1
1
1
2
1
2
2
1
2
2
1
2
1
3
2
1
2
2
2
2
2
1
2
1
2
2
1
1
1
2
2
2
2
2
2
2
1
2
2
2
1
2
2
2
2
2
2
2
2
1
1
2
2
1
1
1
1
1
1
1
2
1
1
2
1
2
1
2
1
2
1
2
2
3
2
2
2
1
2
1
2
2
2
2
1
2
2
2
2
2
1
1
1
2
2
1
1
2
2
1
1
1
2
2
3
2
2
2
1
1
1
2
2
1
1
2
1
2
1
1
3
2
1
3
3
2
1
2
2
2
1
2
3
2
2
1
1
2
3
2
1
1
3
1
2
2
1
1
1
1
3
2
3
2
2
2
2
1
1
2
2
3
1
3
2
1
1
1
1
1
1
1
2
1
1
2
1
2
2
1
2
1
1
2
1
2
1
1
1
2
1
2
1
3
1
1
1
2
2
1
3
2
1
1
3
2
3
2
1
1
3
1
2
2
1
1
3
2
1
2
1
2
2
2
2
1
2
2
3
2
2
3
1
1
3
1
2
3
2
1
2
3
3
3
2
2
2
2
1
1
3
2
1
2
2
1
1
3
1
1
2
1
2
1
2
1
1
1
1
2
2
1
1
1
2
1
2
1
2
1
2
2
2
2
1
2
1
2
1
3
2
2
1
1
2
1
2
2
3
1
2
2
1
2
2
1
2
2
1
1
2
2
1
2
2
2
1
2
1
1
2
1
1
1
2
2
1
2
1
3
2
2
2
3
2
1
2
1
2
2
1
1
2
1
2
2
1
2
2
2
1
1
2
1
2
2
2
1
1
2
1
2
2
2
1
2
1
1
1
1
1
1
1
1
1
2
2
2
2
2
1
2
2
1
2
1
1
3
2
1
1
1
2
2
2
2
1
2
1
2
2
2
2
2
2
1
2
1
1
1
2
3
2
3
1
1
3
2
2
1
2
3
3
3
2
2
1
1
2
2
2
2
1
2
3
2
3
2
1
2
1
1
2
1
1
2
2
2
2
2
1
1
1
1
1
2
1
1
1
1
2
1
1
2
2
2
2
1
1
2
2
1
1
2
1
1
1
2
2
1
1
1
1
1
2
2
2
1
1
2
2
3
1
2
3
3
1
1
1
1
1
1
2
3
2
1
2
1
2
2
2
2
2
1
2
1
1
1
2
2
2
2
1
1
2
2
3
1
2
2
1
2
1
2
1
2
2
2
1
1
1
3
1
1
2
1
3
1
2
1
1
2
2
3
1
1
2
2
2
3
2
2
1
2
2
2
1
2
2
2
1
1
2
1
2
2
2
2
1
2
2
1
2
3
1
1
2
2
1
1
1
2
2
2
1
1
2
2
2
2
1
3
1
2
1
1
2
1
1
3
2
1
1
1
1
1
1
2
2
1
2
1
2
2
1
1
1
3
2
2
2
2
1
2
2
2
1
2
1
3
3
1
2
2
1
2
2
2
1
1
2
2
2
3
2
1
1
1
2
1
2
3
1
2
1
2
1
1
1
1
1
3
2
3
1
1
1
2
1
1
1
1
1
1
2
1
2
2
2
2
3
2
1
2
1
2
1
1
2
2
1
1
1
2
2
2
1
1
1
1
1
2
2
1
2
1
2
1
1
1
2
1
1
1
1
1
2
1
2
1
3
1
2
1
1
2
2
2
1
1
2
3
1
1
1
1
3
1
2
1
1
1
2
1
2
2
2
1
3
1
1
2
2
2
3
1
2
2
2
2
3
2
2
1
1
1
2
2
1
2
2
1
2
1
2
2
3
1
2
1
2
3
2
1
1
3
1
1
1
1
2
1
3
1
1
1
1
2
1
2
2
2
1
1
2
2
3
1
1
1
1
1
1
2
3
2
2
1
1
1
2
2
2
2
1
2
2
2
2
1
2
1
1
1
2
1
2
2
1
2
1
1
2
2
2
1
1
1
1
2
3
1
1
2
1
2
2
1
1
1
1
3
2
1
2
1
2
2
2
1
2
1
2
1
1
1
2
1
2
2
1
1
2
1
1
1
1
2
2
1
1
1
2
1
2
1
3
1
2
3
1
1
2
1
1
2
2
1
2
2
2
1
3
1
2
1
2
2
2
1
3
2
2
1
1
2
2
3
2
2
1
1
2
3
1
2
1
1
1
1
2
2
2
2
1
1
3
1
1
1
2
2
2
2
1
2
2
3
2
2
1
1
2
2
2
2
3
1
1
2
1
1
1
2
1
3
2
1
1
3
3
1
1
1
1
2
1
1
1
3
1
1
1
1
2
2
1
3
1
2
1
1
1
1
2
1
2
1
1
2
1
1
1
1
1
1
2
1
2
1
2
2
2
1
1
2
2
3
2
2
1
3
2
1
1
1
2
1
1
1
2
2
2
1
2
3
2
1
2
2
1
2
2
1
2
2
2
2
2
2
2
2
1
1
2
1
1
2
2
3
1
1
1
2
1
1
1
2
1
1
3
1
1
1
2
2
1
2
2
2
1
2
1
1
1
2
2
2
1
2
2
1
1
1
2
2
2
2
3
2
1
2
2
1
2
3
1
2
2
1
2
1
2
2
2
2
1
1
1
3
2
2
1
2
2
2
1
2
1
2
2
1
2
1
1
2
1
2
2
1
2
2
1
1
1
1
1
1
2
1
1
1
1
1
2
2
2
2
2
1
2
1
2
2
1
2
2
2
2
2
1
2
3
2
2
1
1
2
1
2
3
2
1
1
2
3
3
2
2
2
1
1
2
2
2
1
2
2
1
2
1
2
2
2
1
1
2
1
1
1
2
1
1
2
1
3
2
2
2
2
2
1
2
2
2
1
2
1
1
1
1
1
2
3
1
1
2
1
1
3
3
1
2
3
2
1
2
2
1
1
2
2
2
2
2
1
1
1
1
2
1
1
2
2
1
1
3
3
2
1
2
2
1
2
2
2
2
2
1
2
1
3
2
1
2
2
1
2
1
2
1
1
2
2
1
1
2
2
1
1
2
2
2
1
1
1
1
2
1
1
2
2
1
1
2
1
1
1
2
2
3
2
2
2
2
1
1
2
2
1
1
2
1
2
1
3
2
1
2
1
2
2
2
1
2
2
1
1
1
2
3
1
3
1
3
1
1
2
1
2
1
2
1
1
1
2
1
3
1
1
1
3
2
1
2
2
2
2
1
2
2
1
2
1
1
2
3
2
1
2
2
1
2
2
2
2
1
2
2
2
1
2
1
2
2
2
1
1
1
1
2
2
2
2
2
2
1
2
1
1
1
1
2
2
2
2
2
3
2
3
2
1
2
1
1
2
1
2
1
2
2
2
1
2
1
1
2
1
1
2
1
2
2
2
2
1
2
2
3
1
1
2
1
1
1
1
2
1
2
2
2
1
2
1
1
2
2
2
2
2
1
1
2
1
2
2
1
1
1
1
1
1
2
2
2
1
2
1
2
2
2
2
2
1
2
2
2
2
1
2
1
3
1
2
1
2
2
2
1
1
1
2
1
2
3
1
1
1
1
2
2
1
2
2
1
2
2
2
1
3
2
1
3
2
2
2
2
1
2
1
1
1
2
2
1
1
1
2
2
1
2
2
2
2
1
1
1
1
2
1
1
2
2
3
3
1
2
2
1
3
2
1
1
3
1
2
1
2
2
2
1
1
2
2
1
2
1
1
1
2
2
1
1
1
1
1
1
2
2
2
2
1
1
2
2
2
2
1
1
2
2
2
1
2
2
3
1
2
1
1
1
2
1
1
2
1
3
2
3
2
1
1
3
3
2
1
2
1
1
1
2
1
1
2
3
3
2
1
2
1
1
3
1
1
1
1
1
1
1
2
2
1
1
1
1
2
1
1
2
2
1
1
2
2
1
2
1
2
1
2
2
1
1
1
2
2
2
1
2
2
1
1
1
1
3
1
1
1
2
1
3
2
1
2
2
1
1
2
1
1
1
2
1
2
2
1
2
1
2
1
1
2
1
2
1
1
1
1
2
2
2
2
2
1
2
1
3
2
1
2
1
2
3
2
2
2
2
1
1
3
1
1
2
1
1
1
2
1
2
2
1
1
3
2
1
1
3
1
2
2
1
2
2
2
3
2
1
1
1
3
2
2
1
1
2
1
1
2
2
2
2
1
1
1
1
2
2
2
3
2
1
1
2
1
2
2
1
1
1
1
1
1
2
2
2
1
1
1
2
2
3
2
2
1
2
2
2
1
2
2
2
2
1
1
1
2
2
1
2
1
1
2
2
2
2
2
2
2
1
1
1
1
1
1
2
1
2
1
1
2
2
1
1
2
3
1
1
1
2
2
1
2
1
1
1
1
1
3
3
2
2
2
2
2
1
2
1
1
2
2
1
1
1
2
1
2
2
2
2
2
1
3
1
2
1
2
1
2
1
2
1
2
2
2
1
2
2
1
2
1
1
1
1
2
2
2
2
2
3
2
1
1
1
2
1
3
1
1
2
2
3
2
3
1
1
1
3
2
1
1
2
2
2
2
2
2
1
2
1
1
2
3
3
2
2
1
2
1
1
1
1
1
2
2
2
1
2
2
1
1
2
3
2
1
1
2
1
2
2
1
2
1
2
1
1
2
2
1
1
1
1
1
1
1
1
2
1
1
1
1
3
2
1
2
2
1
1
2
2
1
1
3
1
2
2
3
2
1
2
1
1
2
1
1
2
2
2
2
2
3
1
2
1
2
1
2
2
1
2
2
1
2
2
2
2
2
2
1
1
1
3
1
3
2
1
2
1
2
2
2
1
2
2
1
1
2
1
2
1
2
1
1
1
1
1
1
1
2
3
1
2
1
2
1
2
1
1
3
2
2
2
1
2
2
1
1
2
2
1
2
1
1
3
1
2
1
2
1
2
3
1
2
2
2
2
1
1
2
1
2
3
1
2
1
2
1
2
1
1
1
2
1
2
2
2
1
2
1
2
1
2
1
1
1
3
1
1
2
2
2
1
2
2
2
1
2
2
2
1
1
2
2
3
2
1
1
1
1
3
1
2
2
1
1
2
2
1
2
1
1
2
1
2
3
1
2
1
2
2
1
1
1
3
1
2
1
1
2
2
1
2
2
1
2
3
2
1
2
2
2
2
1
2
2
2
1
2
3
2
2
2
2
1
2
2
2
2
1
2
2
3
1
1
1
2
2
1
2
2
1
1
2
2
1
2
3
1
2
3
1
2
1
1
1
2
3
1
1
2
3
2
2
2
1
1
2
2
2
3
1
2
2
1
2
2
2
2
1
2
2
1
1
2
1
2
2
2
1
2
2
2
1
1
1
1
2
2
1
3
1
1
1
1
2
2
2
2
2
2
2
2
1
1
2
1
1
1
2
2
1
1
2
2
2
2
2
1
2
1
2
1
3
3
3
1
2
1
2
1
1
1
1
2
2
1
3
2
1
1
1
1
1
1
2
2
1
1
1
2
1
1
1
2
2
1
1
1
2
1
2
3
1
1
1
1
1
1
2
2
2
2
2
2
2
1
2
1
2
1
2
2
3
1
1
2
1
1
2
1
2
2
2
2
1
2
2
1
1
2
2
2
2
1
2
2
1
3
2
1
1
3
2
2
1
2
2
2
3
3
1
3
2
2
2
1
1
1
2
1
1
3
2
2
3
1
1
2
1
2
2
1
2
1
1
2
1
2
2
2
2
1
2
2
1
2
2
1
2
2
2
1
1
1
1
1
2
2
1
1
1
1
1
2
1
2
1
2
1
2
1
2
2
1
2
1
1
1
1
2
2
3
2
1
1
2
2
1
2
1
2
1
2
1
2
1
1
3
1
1
2
1
3
2
1
2
2
1
1
1
1
2
2
1
2
2
2
2
1
3
1
2
2
2
2
1
1
2
1
1
2
2
3
1
1
2
1
2
1
1
2
2
2
1
2
2
1
1
2
2
1
2
2
1
3
2
2
2
2
3
3
1
2
1
2
2
1
1
2
3
3
1
1
2
2
2
2
2
2
2
1
1
1
2
1
2
2
1
2
2
2
1
1
1
3
1
1
2
2
1
1
1
2
1
2
3
3
1
2
2
2
2
1
2
3
1
1
3
2
2
2
2
1
3
1
1
2
1
2
2
2
1
2
1
1
2
1
2
2
2
1
1
2
2
2
1
1
1
2
1
1
2
2
1
2
1
1
3
1
1
2
2
1
3
1
3
3
1
1
2
2
2
1
2
2
1
2
1
1
2
1
1
3
3
2
2
2
1
2
1
1
2
1
2
2
1
2
2
2
2
1
2
1
3
2
2
2
1
2
2
2
1
2
2
2
1
2
3
2
3
2
3
1
2
2
1
2
1
2
1
2
1
1
2
2
1
2
2
2
1
1
2
1
2
1
2
1
3
1
2
2
1
1
2
2
2
1
2
2
2
2
1
2
1
2
1
2
1
2
2
1
2
1
2
3
1
2
2
1
1
1
2
2
2
3
1
2
2
3
2
1
1
2
1
2
1
2
1
1
2
1
1
1
1
1
1
2
3
1
1
1
2
2
2
1
1
2
1
2
2
1
1
1
1
2
3
1
1
2
2
1
2
3
2
2
1
1
2
1
2
1
1
2
2
2
2
2
2
1
2
1
2
2
2
1
2
2
1
1
2
3
1
1
2
2
2
1
1
2
2
2
1
2
3
2
1
1
1
2
1
1
1
2
2
1
2
2
1
2
1
1
1
1
1
1
2
1
2
2
2
2
1
2
1
2
2
2
2
1
2
1
1
2
1
1
2
2
2
3
1
2
1
2
1
1
1
1
2
1
2
1
1
2
2
2
2
2
1
1
3
1
1
2
2
2
3
1
1
2
1
2
1
1
2
1
3
2
3
2
2
1
2
1
1
2
1
1
1
2
2
1
1
1
2
1
1
1
2
2
1
2
1
1
2
1
2
2
1
2
1
1
1
1
2
2
2
2
1
1
2
1
2
1
2
3
1
2
2
1
1
2
1
1
3
2
2
2
1
2
1
2
2
2
1
2
1
3
2
1
3
2
1
2
1
1
2
1
2
2
2
2
2
2
2
1
3
1
2
2
1
2
1
3
1
1
2
2
1
2
1
2
1
2
2
2
2
1
2
2
1
2
2
1
2
1
2
2
3
2
3
1
2
1
2
1
2
2
1
1
2
1
1
2
1
2
2
2
1
2
1
1
1
1
1
2
1
3
1
2
1
2
1
1
1
3
1
1
2
1
1
3
3
2
1
1
2
1
1
1
1
1
1
2
2
2
2
2
1
1
1
2
2
1
1
1
1
1
1
1
1
2
2
1
1
2
2
2
2
2
1
2
1
2
1
1
2
2
1
2
1
2
1
1
1
2
2
2
3
2
2
1
1
1
2
1
2
1
2
2
1
2
3
1
1
1
1
2
1
3
2
1
1
1
1
2
1
1
2
1
1
1
1
2
3
2
1
1
2
2
1
2
1
3
2
1
2
1
1
1
2
2
1
2
2
1
2
3
3
1
3
2
1
2
2
1
1
2
1
2
2
2
1
3
2
1
2
2
1
1
2
1
2
1
2
1
2
2
2
2
1
2
3
1
2
2
1
1
1
1
2
2
1
2
2
1
1
1
1
2
3
1
3
2
2
1
2
1
1
2
3
2
1
2
2
2
2
3
3
2
2
2
1
1
1
2
1
1
2
1
3
1
2
1
2
1
1
1
2
1
2
1
2
1
2
2
2
2
1
2
1
1
2
1
1
2
2
1
2
1
2
2
1
1
1
2
2
2
1
1
2
2
2
1
2
1
1
2
2
2
2
1
2
2
2
1
1
2
2
1
1
3
2
1
1
1
1
2
2
1
1
2
2
2
1
1
2
2
1
2
1
2
2
2
2
2
2
1
2
1
1
3
1
1
2
2
2
2
2
1
1
1
2
3
1
2
1
1
1
2
2
1
2
2
1
1
1
1
2
2
2
3
2
2
1
2
2
3
3
2
2
1
2
1
2
2
2
2
2
1
2
2
2
1
2
2
1
2
1
2
1
1
1
2
1
1
2
1
1
1
2
1
2
2
1
1
3
2
2
1
2
2
1
2
1
2
1
2
1
1
2
2
1
2
2
1
2
1
1
1
2
1
2
2
2
2
1
1
1
3
1
1
2
3
2
1
1
1
2
1
2
2
2
2
1
2
2
1
1
2
2
1
2
1
3
2
2
2
1
1
1
2
2
3
1
2
1
2
1
2
2
1
2
2
1
1
3
1
1
2
2
1
1
1
2
1
3
1
2
3
1
2
1
1
3
2
2
2
2
1
2
2
2
2
2
2
1
2
2
1
2
1
2
1
1
1
2
2
1
1
1
1
2
1
1
1
2
2
3
2
2
1
2
2
2
2
1
2
1
3
1
2
1
2
2
2
2
2
1
3
2
2
1
1
2
2
1
1
1
2
3
2
2
1
2
2
1
1
2
1
2
1
2
1
2
2
2
2
2
2
1
2
3
2
1
2
1
2
1
2
3
1
1
3
2
1
2
2
2
1
2
1
1
3
1
1
1
2
2
2
2
1
1
2
1
1
2
2
2
1
1
1
1
3
2
2
1
2
2
1
2
1
1
2
2
2
2
2
1
3
1
1
2
1
3
1
2
1
1
2
1
1
2
1
3
2
1
3
1
2
1
2
2
2
1
2
1
2
2
1
2
1
1
2
1
1
2
2
1
2
1
1
2
1
1
3
2
1
1
2
2
2
2
3
1
2
3
2
2
2
1
1
1
1
2
1
1
1
1
1
2
1
1
3
1
2
2
1
1
2
1
2
2
2
2
2
1
1
1
2
1
1
1
1
1
1
2
1
2
1
2
1
2
2
1
1
2
2
2
1
1
3
2
1
2
1
1
2
2
1
3
3
2
1
1
2
1
1
2
2
1
1
1
2
2
1
1
2
2
1
1
1
2
1
1
1
2
3
2
1
2
1
1
2
2
1
1
1
2
2
2
2
2
1
2
1
2
1
1
1
2
1
2
3
2
2
1
3
2
2
2
1
2
1
1
1
1
1
2
1
1
1
1
2
1
1
2
1
2
2
1
2
2
1
1
2
1
2
2
1
2
2
3
2
2
1
1
2
2
2
2
1
1
1
1
2
1
1
2
1
2
2
1
2
1
1
1
2
1
2
2
3
2
1
2
3
2
1
1
1
2
1
1
2
2
1
2
1
1
2
2
2
1
2
1
1
2
1
1
1
1
1
3
2
1
2
2
1
2
2
2
1
2
2
2
2
1
2
2
1
1
2
2
2
1
1
1
2
2
1
1
1
1
3
2
1
1
3
2
1
2
2
1
1
1
1
2
1
2
2
2
1
2
3
2
2
2
1
2
1
2
3
2
2
2
1
1
2
2
2
1
2
1
3
1
1
1
1
1
1
2
2
3
1
2
3
1
2
3
1
2
1
1
1
1
1
2
2
2
2
2
2
2
1
3
1
2
2
2
2
3
1
2
2
3
1
1
2
3
2
2
2
2
1
1
2
2
1
1
2
1
2
2
1
2
1
1
1
2
1
2
2
2
1
2
1
1
1
1
2
2
2
2
2
3
2
2
3
1
2
1
3
2
1
1
1
1
2
1
3
1
1
1
2
3
2
2
2
1
2
2
2
2
2
2
2
2
1
1
1
2
1
1
2
1
2
3
1
2
3
2
2
1
1
1
2
1
2
2
2
2
2
1
1
1
3
2
2
2
2
2
1
1
2
2
2
1
1
1
3
2
1
1
2
2
2
2
1
1
1
1
1
1
2
1
1
1
1
2
2
1
1
1
3
2
2
2
2
2
3
1
1
2
1
1
3
2
2
2
1
2
1
2
3
1
2
2
1
3
1
1
2
2
2
2
2
2
1
1
2
3
1
2
1
2
1
2
1
2
1
1
1
2
1
3
2
1
2
2
2
2
1
2
2
2
1
1
1
3
2
2
2
1
1
1
2
2
2
2
2
2
1
1
2
1
1
1
1
2
3
2
1
2
1
2
1
2
1
2
2
2
1
2
1
2
1
1
2
2
1
1
3
2
2
2
1
1
1
2
1
2
1
1
2
1
1
2
1
3
2
1
1
2
1
2
1
1
1
1
3
1
2
1
2
2
2
1
1
1
2
3
2
1
2
2
1
1
2
1
3
3
1
1
2
1
1
3
2
1
2
1
1
2
1
1
1
2
1
1
2
2
2
1
1
1
2
1
2
1
1
2
1
2
1
2
1
2
2
1
1
2
1
2
2
2
2
2
2
2
1
2
1
1
2
2
2
1
2
1
2
2
1
1
2
2
3
1
1
2
1
2
2
1
2
2
3
1
1
1
2
3
1
2
2
1
2
2
1
1
1
1
2
2
1
2
2
2
2
2
2
2
2
2
1
2
1
2
2
1
1
1
1
1
1
1
2
1
2
2
2
1
1
2
2
3
2
1
1
2
2
1
3
2
2
1
1
1
2
2
3
1
1
2
2
3
2
2
2
2
1
1
1
2
3
2
2
2
1
1
1
1
1
2
1
1
2
2
1
3
1
1
1
2
1
2
2
2
1
1
1
1
3
2
1
3
2
1
2
2
2
1
1
1
2
1
1
1
1
1
1
3
3
1
1
2
1
1
2
1
1
1
1
1
2
2
1
1
1
2
1
1
2
1
1
2
2
1
2
2
2
1
2
2
2
2
1
2
1
2
3
3
1
3
2
2
2
1
2
1
1
2
2
1
2
2
2
2
1
2
2
1
1
1
3
1
1
2
2
2
1
1
1
1
1
1
2
2
3
1
1
1
1
1
1
1
2
3
2
1
3
1
1
1
1
2
2
2
2
1
1
1
2
1
1
1
1
1
2
1
2
1
1
1
2
2
2
1
2
1
2
1
1
2
2
1
1
2
1
1
2
1
3
2
2
2
2
1
1
1
2
2
2
2
2
2
2
1
2
2
2
3
2
2
1
2
2
1
1
2
1
1
1
1
1
2
1
2
1
1
2
2
1
3
2
1
2
1
2
1
3
1
2
2
2
2
1
1
2
1
2
3
2
1
3
1
2
2
1
3
1
2
2
1
2
1
2
1
2
2
2
3
1
1
2
1
1
3
3
2
2
2
2
2
1
1
1
2
2
2
2
2
1
1
2
2
2
1
2
2
2
2
1
2
3
2
2
1
2
2
1
1
1
3
2
3
1
1
1
2
2
1
2
2
1
1
2
1
1
1
2
2
2
2
1
1
2
3
2
1
1
2
2
2
1
3
1
2
1
2
2
1
2
1
3
2
1
1
1
2
1
1
1
1
2
2
1
1
1
1
2
2
1
2
3
1
2
1
1
2
3
3
1
3
2
1
2
1
2
1
1
2
1
2
2
1
2
1
2
2
2
1
1
2
1
2
2
1
1
2
1
1
2
1
1
3
1
1
2
1
1
1
1
2
2
2
2
1
2
1
1
2
1
2
2
1
2
1
1
1
2
1
2
2
2
2
2
2
3
2
2
1
3
2
2
1
3
1
1
2
1
2
1
2
1
2
2
1
2
2
2
2
2
2
2
2
1
2
3
1
3
1
1
2
2
3
1
2
2
1
2
1
2
2
1
2
2
2
2
2
1
1
2
3
2
3
2
2
1
1
3
2
1
1
2
3
2
1
2
3
2
2
3
2
3
2
3
2
1
2
2
2
2
2
1
2
2
1
2
3
2
1
2
2
2
1
2
1
2
3
2
2
1
2
2
1
3
2
1
2
2
2
1
2
2
1
2
1
2
1
2
1
1
1
2
2
2
1
1
2
1
2
1
1
1
2
1
1
2
1
2
2
1
3
2
1
1
1
1
1
2
2
1
1
1
2
1
1
3
3
2
1
2
2
1
2
3
1
2
1
1
1
1
1
2
2
1
3
3
1
1
1
2
2
2
2
3
2
1
2
2
2
1
2
1
1
2
2
3
3
2
1
2
1
2
2
1
1
3
3
2
3
2
3
2
1
1
1
2
2
1
2
1
1
3
1
2
3
1
2
2
2
1
1
1
2
2
2
1
1
2
1
2
1
3
3
1
2
3
2
2
2
2
2
2
3
2
1
1
1
2
2
1
2
2
2
2
1
2
2
1
1
1
2
1
1
1
2
1
2
2
1
1
2
1
2
1
1
2
2
1
2
2
2
1
3
2
2
1
2
2
1
2
3
1
1
2
3
2
2
2
2
1
1
2
1
1
1
1
1
2
1
2
1
2
1
2
2
1
3
2
1
2
2
1
1
1
2
2
2
2
1
1
2
1
2
1
1
3
2
2
1
1
3
1
1
2
1
1
2
1
1
2
1
2
1
1
1
2
2
1
1
2
1
2
1
3
1
2
1
3
3
2
1
1
2
1
1
1
1
1
1
1
1
3
1
1
2
1
1
2
1
1
1
2
3
2
1
1
1
1
1
1
2
1
1
2
1
2
1
1
2
2
2
2
2
1
2
2
2
1
1
2
2
1
1
3
1
1
1
1
2
2
1
2
2
3
1
2
2
2
2
2
2
2
1
1
2
2
2
2
3
2
1
2
1
2
1
2
2
1
3
1
1
2
2
2
2
2
2
1
2
3
2
3
1
3
2
2
2
2
1
2
2
1
1
2
2
1
2
2
1
2
1
1
3
1
3
1
1
1
2
3
2
2
1
1
2
2
1
1
3
1
1
1
1
2
2
2
2
1
1
1
2
2
2
2
3
2
1
1
1
1
1
2
1
2
1
2
2
1
2
1
2
1
1
1
1
1
2
1
1
1
1
1
2
1
1
2
1
2
2
2
1
3
3
1
2
1
1
1
1
1
1
1
2
3
1
2
2
2
1
2
2
1
2
2
2
1
3
1
2
3
2
2
1
2
3
1
1
2
1
1
1
2
1
2
1
1
2
2
1
1
2
2
1
1
3
1
3
2
2
2
2
2
1
2
1
1
1
2
2
2
1
2
1
2
3
1
1
2
1
1
2
2
2
1
1
1
2
3
2
1
2
1
1
1
1
2
1
3
2
1
1
2
2
2
1
2
2
2
2
3
1
1
2
1
1
3
1
1
1
2
1
2
2
2
2
2
2
3
1
3
2
1
1
2
3
2
1
1
1
2
2
2
1
2
1
1
1
1
3
1
2
2
1
3
2
1
3
2
1
1
1
1
2
2
1
2
2
2
1
3
1
2
2
2
1
2
2
1
1
2
3
2
1
1
1
1
2
1
2
2
1
2
2
1
1
1
1
2
2
1
3
1
1
1
1
1
2
2
2
1
1
3
2
1
1
1
1
3
2
2
2
1
2
1
1
2
2
2
2
1
1
1
2
1
2
2
1
2
2
1
2
1
2
2
1
1
2
1
1
2
1
2
1
1
2
2
1
1
1
2
1
2
3
1
2
1
2
2
1
1
1
2
2
2
1
1
2
2
2
1
2
1
2
1
2
3
1
2
1
2
1
1
3
1
1
3
1
1
2
2
2
2
1
1
3
1
2
2
1
2
2
1
2
1
1
2
1
2
2
2
1
2
1
1
1
1
2
2
3
1
1
2
2
2
1
2
3
1
1
1
1
1
2
3
1
2
3
1
2
1
1
1
2
2
1
1
2
3
3
1
1
1
1
1
2
2
2
2
1
3
2
1
2
3
2
2
2
1
3
3
2
2
2
1
2
3
2
1
2
2
2
1
1
2
2
2
2
1
2
2
2
3
1
1
3
2
1
1
2
2
2
2
1
2
2
1
1
2
2
2
2
1
2
2
1
2
2
1
1
2
3
3
2
2
1
1
1
2
2
1
2
2
2
2
2
2
1
2
1
1
1
1
2
1
1
2
1
2
2
2
1
1
2
1
2
1
1
3
2
1
1
2
2
1
2
1
2
2
2
2
2
1
2
1
2
1
1
1
1
1
2
2
1
1
2
3
2
2
1
1
1
2
2
1
1
2
2
2
2
1
2
2
1
1
1
3
2
1
2
1
2
1
1
1
2
2
1
1
2
2
2
2
1
2
2
1
2
2
1
2
2
1
1
1
1
1
1
2
1
1
2
2
1
2
2
2
1
2
2
2
2
1
2
2
2
1
3
1
2
1
1
2
2
3
1
1
1
1
1
1
2
2
1
1
1
2
2
2
2
1
1
2
2
2
2
2
1
1
1
1
1
1
1
2
2
3
3
1
1
1
1
1
1
3
1
1
3
1
2
2
2
2
2
1
2
1
1
1
2
2
2
2
2
3
1
1
2
2
2
2
1
2
1
2
3
2
1
3
2
2
1
2
1
1
3
1
2
3
1
2
2
1
2
1
2
1
1
2
1
2
2
1
2
2
2
2
1
2
2
2
1
3
1
3
3
2
1
2
2
2
2
1
3
3
2
1
1
2
2
1
2
1
2
2
2
2
2
2
1
2
2
2
1
1
1
1
2
1
1
2
2
2
1
2
1
1
1
2
2
2
1
1
1
2
3
2
1
1
1
3
2
2
1
2
1
2
2
2
1
1
1
2
2
2
2
2
2
1
2
2
2
2
2
2
2
2
1
2
2
1
1
1
2
2
1
2
1
2
1
2
2
3
2
3
1
2
2
2
1
2
2
2
1
3
3
1
1
1
1
1
3
3
1
2
2
2
2
3
2
1
1
1
1
2
2
2
2
3
2
3
1
1
1
2
1
2
1
2
3
1
2
2
1
1
1
1
3
1
1
2
2
1
2
1
1
2
1
1
1
1
1
1
2
2
2
2
1
3
1
1
2
2
2
1
1
2
1
2
1
3
1
1
2
1
2
1
1
2
2
2
2
2
2
3
2
1
3
2
3
2
2
2
1
1
1
1
1
1
1
1
2
2
1
3
2
3
1
2
1
2
2
1
1
1
2
1
1
1
2
1
3
1
2
2
3
1
3
2
2
3
2
1
1
2
2
2
2
2
3
1
2
1
2
2
2
1
2
2
2
2
2
1
2
2
3
2
1
1
2
2
1
1
3
2
1
2
1
1
2
1
3
2
1
1
1
2
2
2
1
2
1
2
2
2
2
2
1
1
2
2
2
1
2
1
2
1
1
2
1
2
3
2
1
2
2
1
2
2
2
2
2
2
2
2
3
3
1
2
1
2
1
2
1
3
2
1
2
1
1
1
1
1
2
3
2
1
2
1
2
1
1
2
3
1
1
2
2
2
1
2
2
2
2
2
2
3
2
2
1
2
1
2
1
2
1
2
1
2
2
2
1
2
1
2
1
1
1
2
2
2
1
1
2
2
1
2
2
1
1
1
1
1
1
2
1
3
2
2
1
1
1
2
2
2
1
2
1
1
3
1
2
1
2
2
2
2
1
1
1
2
1
1
1
3
2
2
1
2
2
2
2
1
2
2
2
1
3
2
1
2
1
1
2
2
1
1
2
1
1
1
2
2
2
1
1
3
2
2
2
1
1
3
3
2
2
1
1
1
2
2
1
1
1
2
1
2
1
2
1
1
3
1
1
1
1
1
1
1
2
3
2
1
1
2
2
1
1
1
1
1
2
2
1
3
2
2
2
2
1
2
2
1
1
2
1
1
2
1
2
1
2
1
3
1
2
2
2
1
2
2
2
2
2
1
1
2
1
1
1
2
3
2
3
2
1
2
1
2
2
1
2
1
1
2
1
1
2
3
3
2
2
2
2
2
1
2
1
2
1
2
1
1
2
2
2
2
2
3
2
1
1
1
1
2
2
2
1
2
2
1
2
2
2
3
2
1
1
2
2
2
2
1
1
2
2
2
1
2
1
1
2
1
1
1
2
2
1
1
1
2
1
2
2
1
1
1
1
1
1
2
1
1
2
1
1
2
2
1
1
2
2
2
2
1
2
2
2
2
1
2
3
2
1
2
2
1
3
1
3
3
3
2
1
3
1
1
1
1
1
2
1
2
2
1
2
1
2
2
1
2
1
2
2
1
3
1
1
1
2
3
1
1
1
2
1
1
2
2
2
2
1
2
2
2
1
1
1
2
1
2
2
1
2
3
1
2
1
1
2
1
1
1
1
2
1
1
1
2
2
2
2
1
1
2
1
1
2
1
2
2
2
2
2
2
1
1
2
1
2
1
3
2
1
2
2
1
1
2
1
2
1
2
2
1
1
3
1
3
2
2
2
1
1
1
2
1
2
2
2
1
1
1
2
1
1
2
1
2
2
1
1
1
2
1
1
2
2
2
2
2
1
1
2
1
1
2
1
2
1
2
1
2
2
2
2
2
1
1
2
3
1
2
1
2
2
1
1
1
1
2
2
2
2
2
1
1
2
2
1
2
2
2
1
1
2
2
1
1
1
1
3
1
1
2
1
1
1
1
2
1
2
1
2
2
2
2
1
2
3
2
1
2
2
1
1
3
2
1
1
2
1
2
3
1
1
1
2
3
1
2
1
1
2
2
2
3
1
1
2
1
2
1
3
2
2
1
2
2
1
1
1
1
1
1
1
1
2
1
2
2
1
2
1
1
3
2
1
2
1
1
2
2
2
1
1
1
2
2
2
1
2
1
2
2
2
2
2
1
1
1
2
1
2
2
1
2
1
2
1
2
2
2
2
3
2
1
1
1
1
2
2
2
2
2
2
2
1
1
2
2
1
1
1
2
1
2
1
1
1
2
2
2
2
1
2
1
1
1
3
1
2
1
1
2
1
2
2
1
2
1
2
2
1
1
2
2
1
1
1
2
2
2
2
1
1
1
1
1
1
2
2
2
2
1
1
1
1
2
1
2
1
1
2
1
2
1
2
2
2
2
1
1
2
2
2
2
2
1
1
2
3
2
3
2
2
3
1
2
1
2
2
1
2
1
1
3
1
1
1
2
2
2
1
1
1
3
1
1
2
1
2
2
2
1
2
2
2
1
1
1
2
2
2
2
1
2
1
2
3
3
2
2
1
2
1
2
2
1
1
2
2
3
2
2
1
2
1
2
1
2
2
1
1
2
1
2
1
1
3
2
1
2
1
1
1
3
2
2
1
2
1
1
2
1
1
3
3
2
2
1
1
2
1
1
1
1
3
2
2
1
2
1
2
2
2
3
2
2
1
2
1
1
2
2
2
1
1
3
2
2
2
2
2
1
2
1
2
2
2
2
2
1
3
1
1
2
1
2
2
2
2
1
1
2
2
2
2
2
1
1
2
1
3
1
1
2
1
1
1
2
2
3
2
2
3
2
1
1
1
2
1
1
1
1
1
2
1
2
1
2
1
2
1
2
2
3
3
2
1
1
2
1
2
1
2
1
1
1
1
3
1
2
1
2
1
2
1
1
1
1
1
1
1
2
2
1
1
2
1
2
2
1
2
1
2
1
1
1
2
2
1
2
1
3
2
2
3
1
2
2
1
2
1
2
2
2
1
1
2
1
1
2
1
1
1
1
1
2
2
1
2
1
1
1
2
1
Difference
Generator Parameters
--n_high 5 --n_low 1 --q_high 10000 --q_low 10000