Minimum Black-White Bead Chain

You are a craftsman working in the ancient alleys. A customer orders you to create a black‐and‐white bead chain. The chain is a string of beads where each bead is either black or white. The customer gives you k conditions. Each condition is specified by two integers \(x\) and \(y\) and requires that there exists at least one contiguous substring of the bead chain of length \(x\) that contains exactly \(y\) black beads.

Your task is to construct a bead chain that satisfies all the conditions while having the minimum possible length. In addition, for each condition you must output the starting and ending positions (1-indexed) of a substring that meets the required condition.

Note: A substring is defined as a consecutive segment of the bead chain.

Hint: One way to design a solution is to view each condition \((x,y)\) as a pattern of length \(x\) that contains exactly \(y\) black beads. For instance, you may choose the pattern \(B^yW^{x-y}\) (i.e. \(y\) black beads followed by \(x-y\) white beads). Then, the problem reduces to finding the shortest string that contains every one of these patterns as a substring (i.e. the shortest common superstring). Since the number of conditions can be small, a bitmask dynamic programming approach is feasible.

inputFormat

The first line contains an integer \(k\) (the number of conditions). The next \(k\) lines each contain two integers \(x\) and \(y\) representing a condition.

For each condition, you are to form a pattern string where the first \(y\) characters are B (black) and the remaining \(x-y\) characters are W (white).

outputFormat

On the first line, output the constructed minimal bead chain (a string consisting only of characters B and W). Then output \(k\) additional lines. The \(i\)-th of these \(k\) lines should contain two integers, representing the starting and ending positions (1-indexed) of a contiguous substring of the bead chain that satisfies the \(i\)-th condition.

sample

2
3 2
2 1

BBW
1 3
2 3