MofK mới mở một startup công nghệ tên là MicrosOFK. Nhờ tài ăn nói của mình, MofK đã tuyển được ~n~ nhân viên. Dù vậy, để thuyết phục họ về làm việc, MofK đã phải chấp nhận yêu cầu về giờ làm việc của họ; cụ thể, nhân viên thứ ~i~ sẽ làm việc từ thời điểm thứ ~l_i~ đến thời điểm thứ ~r_i~ trong ngày (ta giả sử một ngày được chia làm ~10^6~ khoảng thời gian đánh số từ ~1~ đến ~10^6~). Để giúp mọi người hiểu nhau hơn, MofK muốn chia ~n~ nhân viên vào hai bộ phận: frontend và backend (nhân viên của MofK đều có kĩ năng tốt ở cả hai mảng). Sau đó, mỗi ngày MofK sẽ chọn ra hai nhân viên ~i, j~ đến từ hai bộ phận khác nhau và yêu cầu họ làm chung một dự án. Tất nhiên, ~i~ và ~j~ chỉ có thể làm việc cùng nhau khi họ cùng đang ở công ty, do đó thời gian làm việc chung của họ sẽ là phần giao nhau của ~[l_i, r_i]~ và ~[l_j, r_j]~ (nếu hai khoảng này không giao nhau thì thời gian làm việc chung của họ sẽ là ~0~). MofK muốn chọn tất cả các cặp ~(i, j)~ có thể, mỗi cặp đúng một lần, do vậy MofK sẽ mất tổng cộng ~f \cdot b~ ngày để chọn tất cả các cặp, trong đó ~f~ và ~b~ là số nhân viên nằm trong bộ phận frontend và backend.

Để công ty hoạt động hiệu quả nhất, MofK muốn tổng thời gian làm việc chung của tất cả các cặp là lớn nhất có thể. Hãy giúp MofK tìm ra cách chia tối ưu.

Input

Dòng đầu tiên chứa số nguyên dương ~n~, số nhân viên của MofK (~2 \leq n \leq 300 000~).

Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~l_i, r_i~ (~1 \leq l_i \leq r_i \leq 10^6~).

Output

Dòng đầu tiên in ra số ~t~, tổng thời gian làm việc chung lớn nhất tìm được.

Dòng thứ hai in ra một xâu ~s~ gồm ~n~ kí tự, trong đó kí tự thứ ~i~ là ~F~ nếu nhân viên thứ ~i~ được phân vào bộ phận frontend, ngược lại kí tự thứ ~i~ là ~B~.

Nếu có nhiều cách chia đạt được kết quả tối ưu, mọi cách chia đó đều được chấp nhận.

Scoring

Có ~20\%~ số test thỏa mãn ~2 \leq n \leq 20~.

Có ~20\%~ số test khác thỏa mãn ~l_i = 1~ với mọi ~1 \leq i \leq n~.

~60\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

3
1 2
3 4
5 6

Sample Output 1

0
FFF

Sample Input 2

3
1 2
3 4
1 4

Sample Output 2

4
BBF

Notes

Trong ví dụ thứ nhất, giờ làm việc của cả ~3~ nhân viên đều không giao nhau, do vậy mọi cách chia đều cho kết quả ~0~ và đều được chấp nhận.

Trong ví dụ thứ hai, nhân viên ~1~ và nhân viên ~2~ đều có thời gian làm việc chung với nhân viên ~3~ là ~2~; trong khi đó, thời gian làm việc chung của nhân viên ~1~ và nhân viên ~2~ là ~0~. Vậy cách tối ưu là chia nhân viên ~1, 2~ vào một bộ phận và nhân viên thứ ~3~ vào bộ phận còn lại.