Chef Goes Through Segments

All submissions for this problem are available.
Read problems statements in Mandarin Chinese here
Read problems statements in Russian here
Problem Statement
Chef has a sequence of N segments: [L_{1}, R_{1}], [L_{2}, R_{2}], ..., [L_{N}, R_{N}]. He wants to transform the first segment to the last one (with index N). His plan is to do this big deal with a number of transformations: firstly he will transform
the first segment to the second one, then to the third one, then to the fourth one, and so on till Nth one.
Chef can use operation of a single type: shift one segment border by one unit. So, if he has segment [L, R], he can transform it into one of the following segments: [L + 1, R] (we will denote such operation with string L+), [L, R + 1] (will be denoted as R+), [L  1, R] (L), [L, R  1] (R). Chef doesn't like empty segments, therefore he cannot use any operation that makes a segment empty (L = R).
Chef really wants to transform his segment as fast as possible. Please, help him. Find the sequence with minimal number of operations that transforms his segment. If there are multiple such sequences pick the lexicographically minimal one.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of segments Chef has.
The following N lines contain pairs of integers. The ith line contains integers L_{i}, R_{i}, denoting ith Chef's segment.
Output
For each test case print an answer  two lines. The first line should contain the minimal number of operations. The second line should contain the sequence of operations
without any whitespaces.
Constraints
 1 ≤ T, N ≤ 1000.
 1000 ≤ L_{i} < R_{i} ≤ 1000.
The total sum of N values for all test cases doesn't exceed 1000.
Example
Input: 4 3 1 0 0 1 3 5 1 0 1 3 2 1 2 1 2 0 4 4 6 3 5 1 1 1 2 Output: 9 R+L+R+L+R+L+R+L+R+ 0 1 R+ 13 LRLLLLRRRRL+R+L+
Author:  gerald 
Tester:  rustinpiece 
Editorial  http://discuss.codechef.com/problems/GERALD03 
Tags  cook41, easy, gerald, greedy 
Date Added:  13112013 
Time Limit:  1 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, TCL, PERL6, TEXT, PYP3, 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. 