1 1000
A 0 B 1
A 1 B 0
A 0 B 1
B 0 A 0
B 1 B 1
B 0 A 0
A 1 B 1
A 1 B 1
A 1 B 0
A 0 B 1
A 0 B 0
B 1 A 1
B 0 A 0
B 0 A 0
A 1 B 0
A 1 B 0
B 1 A 0
B 0 A 0
A 1 B 1
A 1 B 1
B 0 A 1
B 0 A 1
A 0 B 1
B 0 A 1
A 1 B 0
A 1 B 1
B 1 A 0
B 1 A 0
B 1 A 0
A 1 B 0
A 0 B 1
A 0 B 1
A 0 B 0
B 0 A 0
A 1 B 1
B 0 A 1
B 0 A 1
B 1 A 0
A 0 B 0
A 1 B 1
A 0 B 0
A 0 B 0
A 0 B 0
B 1 A 0
A 1 B 1
B 1 A 1
B 0 A 0
B 1 A 1
B 1 A 1
B 0 A 0
A 0 B 0
B 0 A 1
B 1 A 0
B 1 A 0
A 0 B 1
B 1 A 1
B 1 A 0
B 1 A 1
B 1 A 1
B 0 A 1
A 0 B 0
A 0 B 1
A 0 B 1
A 0 B 1
B 1 A 0
B 0 A 1
A 0 B 1
A 1 B 1
A 0 B 1
B 0 A 0
A 0 B 0
B 0 A 0
B 0 A 1
B 0 A 1
A 1 B 1
B 0 A 0
B 0 B 0
B 1 A 1
A 0 B 0
A 1 B 0
B 0 A 0
B 1 A 0
A 0 B 0
A 1 B 0
A 0 B 1
B 0 A 0
A 0 B 1
B 0 A 0
A 1 B 1
A 1 B 0
B 0 A 1
A 1 B 1
A 0 B 1
B 1 A 0
B 1 A 0
B 0 A 0
A 0 B 0
A 1 B 0
B 0 A 0
A 0 B 1
B 1 A 0
B 1 A 0
A 1 B 1
A 0 B 1
B 0 A 1
A 1 B 1
B 1 A 1
B 0 A 1
A 1 B 0
B 1 A 0
A 1 B 1
B 0 A 0
B 0 A 1
A 1 B 0
B 0 A 1
A 1 B 0
B 0 A 0
B 1 A 0
A 0 B 1
A 1 B 0
A 0 B 0
A 0 B 0
A 0 B 0
B 1 A 1
A 1 B 0
B 1 A 1
B 0 A 0
A 1 B 0
B 1 A 1
B 1 A 1
B 0 A 1
B 1 A 1
A 1 B 1
A 1 B 0
B 1 A 1
A 0 B 1
B 1 A 0
A 1 B 1
B 0 A 1
A 1 B 1
B 0 A 1
B 1 A 1
B 1 B 0
A 1 B 1
B 1 A 1
B 1 A 0
A 1 B 1
B 0 A 1
A 0 B 0
A 1 B 1
A 0 B 0
B 0 A 0
A 1 B 1
B 1 A 0
B 1 A 1
B 0 A 1
A 1 B 0
B 0 A 0
A 1 B 1
B 0 A 1
A 0 B 1
B 0 A 0
A 1 B 0
A 1 B 1
B 0 A 1
A 0 B 1
B 1 A 0
A 1 B 1
A 1 B 0
A 1 B 0
B 1 A 1
B 0 A 0
B 1 A 0
B 0 A 1
B 1 A 1
A 0 B 1
A 1 B 1
A 1 B 1
A 1 B 0
B 1 A 0
A 1 B 0
B 0 A 1
A 0 B 0
A 0 B 0
A 1 B 0
B 0 A 0
A 1 B 1
A 0 B 0
A 0 B 0
B 1 A 1
A 0 B 0
B 1 A 1
B 0 A 1
A 0 B 0
B 1 A 0
A 0 B 0
A 1 B 1
A 1 B 1
B 0 A 1
A 0 B 0
B 1 A 1
B 0 A 1
A 1 B 1
A 1 B 0
A 1 B 1
B 1 A 0
A 1 B 1
B 1 A 0
B 0 A 0
B 0 A 0
B 0 A 0
B 0 A 0
A 0 B 1
B 1 A 0
B 1 A 0
A 0 B 0
A 1 B 0
B 1 A 1
B 0 A 1
B 0 A 0
A 0 B 0
B 1 A 1
A 0 B 0
B 0 A 0
A 0 B 1
A 0 B 1
B 0 A 1
B 1 A 0
A 0 B 0
A 1 B 0
A 1 B 0
A 1 B 1
B 0 A 1
A 0 B 0
B 0 A 0
A 0 B 0
A 1 B 0
B 0 A 0
A 0 B 0
B 1 A 1
A 1 B 1
A 1 B 1
A 0 B 1
A 0 B 1
A 0 B 1
A 0 B 0
A 1 B 1
B 1 A 0
B 1 A 1
A 1 B 0
B 0 A 0
A 0 B 1
B 1 A 1
B 0 A 1
B 1 A 0
B 1 A 0
B 0 A 0
B 0 A 1
A 0 B 0
A 1 B 1
B 1 A 1
B 1 A 0
B 0 A 1
A 1 B 0
A 1 B 1
B 0 A 0
B 0 A 1
A 0 B 0
A 1 B 0
B 1 A 0
A 1 B 1
B 0 A 0
B 1 A 1
B 0 A 0
A 1 B 0
A 1 B 0
A 0 B 1
B 0 A 0
A 0 B 0
A 1 B 1
A 1 B 1
B 1 A 1
B 0 A 0
B 1 A 0
B 0 A 1
B 0 B 0
B 0 A 0
A 1 B 1
B 0 A 1
A 0 B 1
B 1 A 1
B 0 A 0
A 1 B 0
A 1 B 0
A 1 B 1
B 0 A 1
A 1 B 0
B 0 A 1
A 0 B 1
B 1 A 1
B 0 A 0
B 1 A 1
B 0 A 0
A 1 B 1
A 1 B 1
B 0 A 0
A 0 B 1
A 1 B 1
B 1 A 0
A 0 B 1
A 0 B 1
B 0 A 0
A 1 B 1
B 1 A 0
A 0 B 0
A 0 B 1
A 1 B 0
B 0 A 1
A 1 B 1
B 1 A 0
B 1 A 1
A 1 B 0
B 0 A 1
B 1 A 0
B 0 A 1
A 1 B 0
B 1 A 1
A 1 B 0
B 0 A 1
A 0 B 0
A 1 B 0
B 0 A 0
A 0 B 1
B 1 A 1
A 1 B 0
A 0 B 1
A 0 B 1
A 0 B 0
B 1 A 1
A 1 B 0
A 0 B 0
A 0 B 0
A 1 B 0
A 1 B 1
B 1 A 0
B 0 A 0
B 1 A 1
B 0 A 0
A 0 B 1
A 0 B 0
A 0 B 0
B 0 A 0
B 0 B 0
B 0 A 0
A 1 B 0
A 0 B 1
A 0 B 0
B 1 A 1
B 0 A 1
B 1 A 1
A 1 B 0
B 0 A 1
B 1 A 1
A 0 B 1
A 1 B 0
A 0 B 0
B 1 A 1
B 1 A 0
B 1 A 0
A 0 B 1
B 0 A 0
B 1 A 1
A 0 B 1
B 1 A 0
B 1 A 0
B 0 A 1
A 1 B 1
B 1 A 0
B 1 A 0
A 1 B 0
B 0 A 1
B 0 A 0
B 0 A 0
A 1 B 0
B 0 A 0
A 1 B 0
A 1 B 0
B 1 A 0
A 1 B 1
B 0 A 1
A 1 B 1
A 0 B 1
A 0 B 1
B 0 A 1
A 0 B 1
A 1 B 0
A 0 B 1
B 1 A 1
A 1 B 1
A 1 B 1
B 1 A 0
B 0 A 1
A 0 B 1
B 0 A 1
B 1 A 1
B 0 A 0
B 0 A 1
A 1 B 0
A 1 B 1
B 1 A 1
B 0 A 1
B 0 A 0
B 0 A 1
B 0 A 0
B 1 A 0
B 0 A 0
B 0 A 1
B 0 A 0
A 1 B 1
A 0 B 1
A 0 B 1
A 1 B 0
A 0 B 1
A 0 B 0
A 1 B 0
B 0 A 1
A 0 B 0
B 0 A 1
A 0 B 1
B 0 A 0
A 1 B 1
B 0 A 1
A 1 B 0
A 1 B 1
A 1 B 0
A 1 B 1
A 0 B 1
A 0 B 1
A 1 B 1
B 1 A 0
B 1 A 0
B 1 A 1
A 0 B 0
B 1 A 1
A 1 B 0
A 1 B 1
A 1 B 0
A 0 B 1
B 1 A 0
B 1 A 0
B 1 A 0
A 1 B 0
B 0 A 1
A 0 B 1
B 0 A 1
B 1 A 1
A 1 B 1
A 0 B 0
A 1 B 1
A 0 B 0
B 1 A 0
B 0 A 1
A 0 B 1
A 0 B 0
A 0 B 0
B 1 A 1
A 1 B 0
B 1 A 0
A 0 B 1
A 0 B 1
A 1 B 1
B 1 A 0
A 0 B 0
B 1 A 1
A 0 B 1
A 1 B 0
A 1 B 1
A 1 B 0
A 0 B 1
A 1 B 1
A 1 B 1
B 1 A 0
A 0 B 1
B 0 A 0
B 0 A 1
B 0 A 1
B 1 A 1
A 0 B 1
B 1 A 0
B 0 A 1
A 0 B 0
A 1 B 0
B 1 A 0
A 0 B 1
A 1 B 0
A 1 B 1
B 0 A 1
B 0 A 1
A 1 B 1
A 0 B 0
A 1 B 0
A 0 B 1
A 1 B 1
A 0 B 1
B 0 A 1
B 1 A 1
A 0 B 1
A 1 B 0
B 0 A 0
A 1 B 0
A 1 B 1
A 1 B 1
B 1 A 1
B 1 A 1
A 1 B 0
A 1 B 0
B 0 A 1
A 0 B 0
A 0 B 0
A 0 B 1
A 0 B 1
A 0 B 0
A 0 B 1
B 0 A 0
B 0 A 0
A 0 B 1
B 0 B 0
A 1 B 1
A 1 B 1
A 1 B 0
B 0 A 1
B 0 A 0
A 1 B 0
A 1 B 1
A 1 B 1
B 0 A 1
B 0 A 0
B 1 A 1
B 1 A 1
B 1 A 0
B 0 A 1
A 1 B 0
A 0 B 0
A 0 B 1
B 0 A 1
B 1 A 1
B 1 A 1
A 0 B 0
B 0 A 1
B 0 A 1
A 0 B 1
B 0 A 0
B 1 A 0
B 0 A 1
A 0 B 1
A 1 B 0
A 0 B 1
B 0 A 1
B 0 A 0
A 1 B 0
B 1 A 1
B 1 A 1
A 0 B 0
B 1 A 1
A 0 B 0
A 0 B 1
A 1 B 0
A 0 B 0
A 0 B 1
B 0 A 1
B 0 A 0
B 0 A 0
A 1 B 1
B 0 A 0
B 1 A 1
A 0 A 1
B 1 B 1
B 1 A 0
A 0 B 1
A 0 B 1
B 1 A 1
B 1 A 0
A 1 B 0
A 0 B 0
A 0 B 1
A 1 B 0
B 0 A 0
B 1 A 1
A 1 B 0
A 1 B 1
A 0 B 0
A 0 B 0
B 1 A 0
A 1 B 0
B 0 A 0
B 0 A 0
A 0 B 1
A 0 B 1
A 1 B 1
B 0 A 0
B 1 A 0
A 1 B 0
B 1 A 0
B 1 A 1
B 0 A 0
B 1 A 1
A 0 B 0
B 0 A 1
B 1 A 1
B 0 A 0
B 1 A 0
A 0 B 1
B 0 A 1
A 1 B 1
A 0 B 1
A 0 B 1
A 0 B 1
B 0 A 0
B 0 A 1
B 1 A 1
A 1 B 0
B 1 A 0
A 1 B 0
B 1 A 0
A 0 B 1
B 0 A 1
B 0 A 1
B 0 A 1
B 0 A 1
B 1 A 1
B 1 A 0
A 1 B 1
A 1 B 1
A 1 B 0
B 0 A 1
B 1 A 0
B 0 A 0
A 1 B 1
B 1 A 1
B 0 A 0
A 0 B 1
A 0 B 0
B 1 A 0
A 1 B 0
A 1 B 1
B 0 B 1
B 1 A 1
B 1 B 1
B 1 B 0
A 1 B 0
B 1 A 0
B 1 A 0
B 0 A 1
B 0 A 1
B 1 A 1
B 0 A 0
A 0 B 1
B 0 A 0
A 0 B 0
B 0 A 1
A 1 B 0
B 1 A 0
A 1 B 1
A 0 B 0
B 0 A 1
B 1 A 1
A 1 B 0
A 1 B 0
B 1 A 0
A 0 B 0
B 1 A 0
B 1 A 0
B 0 A 0
B 0 A 1
B 1 A 0
B 1 A 0
A 1 B 1
A 0 B 0
A 0 B 1
A 0 B 1
B 1 A 0
A 0 B 1
A 0 B 1
A 0 B 0
A 1 B 1
A 1 B 0
A 0 B 0
B 1 A 1
A 0 B 0
A 0 B 1
A 1 B 0
A 1 B 0
B 1 A 1
B 0 A 0
A 0 B 0
A 1 B 1
B 1 A 0
B 1 A 0
B 0 A 1
A 0 B 1
B 1 A 1
A 1 B 1
B 1 A 0
A 1 B 0
B 1 A 1
A 0 B 0
A 0 B 1
B 0 A 1
A 1 B 0
B 1 A 1
A 1 B 0
B 1 A 1
A 0 B 0
B 1 A 1
B 1 A 0
B 1 A 1
B 1 A 0
B 1 A 0
A 0 B 0
A 1 B 0
B 0 A 1
A 0 B 1
B 1 A 1
B 1 A 1
A 0 B 0
A 0 B 0
A 1 B 1
B 0 A 0
B 1 B 0
A 1 B 1
A 1 B 1
A 0 B 0
A 0 B 1
B 1 A 0
A 1 B 0
A 0 B 0
B 1 A 0
B 1 A 1
A 1 B 1
B 0 A 0
B 0 A 1
A 0 B 0
A 0 B 0
A 0 B 1
B 1 A 0
A 0 B 1
A 1 B 0
A 1 B 0
A 0 B 0
B 0 A 1
A 0 B 0
B 1 A 1
A 1 B 0
B 1 A 1
B 0 A 0
B 0 A 1
A 0 B 0
B 1 A 0
B 1 B 0
B 0 A 0
B 0 A 1
A 0 B 1
A 0 B 1
B 0 A 0
B 1 A 0
B 0 A 0
A 1 B 0
A 1 B 0
A 1 B 0
A 0 A 1
B 1 A 1
B 0 A 0
B 1 A 1
B 1 A 0
A 1 B 1
B 1 A 0
A 1 B 0
A 0 B 1
B 0 A 1
A 0 B 1
A 1 B 1
A 1 B 1
A 0 B 0
A 0 B 1
B 0 A 1
A 1 B 1
B 0 A 1
A 0 B 0
B 0 A 0
B 1 B 0
B 0 A 0
A 1 B 0
A 0 B 1
B 1 A 0
A 0 B 1
B 1 A 1
A 0 B 0
B 0 A 1
B 1 A 0
A 0 B 0
B 0 A 0
A 1 B 1
B 0 A 1
A 1 B 1
B 0 A 0
B 1 A 1
A 0 B 0
B 1 A 1
A 0 B 0
A 1 B 0
A 0 B 0
A 1 B 0
A 1 B 1
B 0 A 1
B 1 A 0
A 1 B 1
B 1 A 1
A 1 B 0
B 1 A 1
B 1 A 1
A 0 B 0
B 1 A 0
A 0 B 1
A 1 B 1
A 1 B 1
B 0 A 1
A 0 B 1
B 0 A 1
B 1 A 1
A 1 B 0
A 1 B 1
A 0 B 0
A 0 B 1
A 0 B 1
B 1 A 0
A 1 B 1
B 0 A 0
B 0 A 1
B 0 A 1
B 1 A 1
A 0 B 0
B 1 A 1
A 0 B 0
A 0 B 0
B 1 A 0
B 0 A 1
B 1 A 0
B 0 A 0
B 1 A 0
A 1 B 0
A 0 B 0
A 1 B 0
B 0 A 0
A 1 B 0
B 1 A 1
B 1 A 0
B 0 A 0
A 1 B 0
A 1 B 1
A 1 B 1
A 1 B 0
B 0 A 1
A 1 B 0
B 1 A 0
B 0 A 0
A 1 B 0
A 0 B 1
A 1 B 0
A 0 B 1
B 0 A 0
B 0 A 0
B 1 A 0
B 0 A 0
B 1 A 1
B 1 A 1
A 1 B 0
B 1 A 1
B 1 A 1
B 0 A 0
A 0 B 0
B 0 A 1
A 0 B 0
A 0 B 1
A 0 B 0
B 0 A 1
B 1 A 1
A 0 B 0
B 1 A 1
A 1 B 0
A 1 B 1
B 0 A 0
B 1 A 0
A 0 B 1
B 1 A 1
A 0 B 1
B 1 A 0
A 0 B 1
A 1 B 1
A 0 B 1
A 1 B 0
B 0 A 1
B 0 A 0
A 0 B 1
B 0 A 0
A 1 B 0
B 0 A 0
A 1 B 1
B 1 A 1
A 1 B 1
A 0 B 1
B 1 A 0
A 1 B 0
B 1 A 0
A 1 B 1
A 0 B 0
A 0 B 0
A 1 B 0
A 1 B 1
B 0 A 0
B 0 A 1
A 0 B 0
B 1 A 1
B 0 A 1
B 1 A 0
B 0 A 1
A 1 B 0
A 1 B 0
B 1 A 1
B 1 A 0
B 1 A 0
B 1 A 1
A 1 B 1
B 0 A 1
A 0 B 0
B 0 A 0
B 1 A 0
A 0 B 1
B 1 A 0
B 1 A 1
A 0 B 1
A 1 B 1
A 0 B 1
A 1 B 1
A 1 B 1
B 0 A 0
B 1 A 1
A 0 B 0
A 0 B 1
B 0 A 0
B 1 A 1
B 1 A 0
A 0 B 1
B 0 A 1
A 1 B 0
A 0 B 1
A 0 B 1
A 0 B 0
A 1 B 0
A 1 B 0
A 1 B 0
B 0 A 0
B 1 A 0
B 0 A 1
A 0 B 0
B 0 A 1
A 1 B 0
A 1 B 1
B 0 A 0
A 0 B 1
B 1 A 0
A 0 B 1
A 0 B 0
A 1 B 1
A 1 B 1
B 1 A 0
B 0 A 0
A 0 B 0
A 0 B 1
A 1 B 1
B 0 A 0
A 1 B 0
A 0 B 0
A 1 B 0
B 0 B 0
B 0 A 0
B 1 A 0
B 1 A 1
B 1 A 0
B 1 A 0
B 1 A 0
A 1 B 1
B 0 A 1
B 0 A 1
B 0 A 1
A 1 B 1
B 1 A 1
B 0 A 1
B 1 A 0
B 0 A 1
A 0 B 0