Byteknights and Byteknaves

All submissions for this problem are available.
A long school holiday has come, and you decided to visit the famous Byte Island. You know there are only two types of Bytelandians: Byteknights and Byteknaves. A Byteknight always tells the truth, whereas a Byteknave always lies.
It is known that there are N Bytelandians in the island, and now you meet all of them. You are curious about their types. Because you are a smart logician, you don't want to ask them questions that immediately reveal their types (that's too boring). Instead, to each Bytelandian you ask, "How many Byteknights are there here?"
To your surprise, they also don't answer your questions directly. Instead, the ith Bytelandian answers of the form "The number of Byteknights here is between a_{i} and b_{i}, inclusive". You record all answers in your pocket note.
Now that you have collected all information you need, determine the type of each Bytelandian.
Input
The first line contains a single integer T, the number of test cases. T test cases follow. The first line of each test case contains a single integer N. N lines follow. The ith line contains two integers a_{i} and b_{i}.
Output
For each test case, output two lines. In the first line, output a single integer indicating the number of different solutions, modulo 1000000007. In the next line, output the lexicographically smallest solution. A solution is a string consisting of N characters, where the ith character of the string is '1' if the ith Bytelandian is a Byteknight, or '0' in case of a Byteknave. It is guaranteed that there is at least one valid solution.
Example
Input: 3 1 0 1 4 1 4 2 4 3 4 4 4 3 1 2 0 0 1 3 Output: 1 1 5 0000 1 101
Constraints
 1 <= T <= 5
 1 <= N <= 50000
 0 <= a_{i} <= b_{i} <= N
Author:  fushar 
Tester:  pieguy 
Editorial  http://discuss.codechef.com/problems/BYTEISLE 
Tags  dec10, easy, fushar 
Date Added:  25102010 
Time Limit:  0.285285 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 