Assistants
Professor Baitazar is overseeing a significant scientific project and has n independent experiments remaining (numbered from 1 to n) to complete the project.
For each experiment, the professor has two options: conduct it himself or delegate it to an assistant. If he chooses to handle the i-th experiment personally, he will need p_i consecutive days, during which he cannot attend to other tasks. Alternatively, if he delegates the experiment, he must spend one day selecting an assistant. This selection day is exclusive, meaning he cannot perform other duties. The assistant will then take over from the following day and complete the experiment in a_i consecutive days. During this period, the professor is free to focus on other activities. It is assumed that a suitable assistant is always available and not yet engaged in the project.
The professor has tasked you with devising a schedule that allows him to complete the project in the shortest possible time.
Input
The first line of input contains an integer n (1 ≤ n ≤ 500000) - the number of experiments remaining for Baitazar to complete the project.
The next n lines each contain two integers p_i and a_i (1 ≤ p_i ≤ a_i ≤ 10^9), which represent the number of days required for the i-th experiment if conducted by the professor and by an assistant, respectively.
Output
On the first line, output a single integer k - the minimum number of days needed to finish the project. In the following n lines, provide the schedule for the experiments that achieves this minimum duration.
Each of the next n lines should describe the schedule for the i-th experiment: first, the letter "B" if the professor conducts the i-th experiment himself, or "A" if he delegates it to an assistant, followed by a space and the number t_i (1 ≤ t_i ≤ k) - the day on which the professor will begin the experiment (which will end on day t_i+p_i-1), or the day on which he will select the assistant (who will work from day (t_i+1) to day (t_i+a_i)).
If there are multiple optimal schedules, you may output any one of them.