Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Extended Normal Order Sort
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 428Accepted: 96

Description

When sorted in standard order, strings with digits in them may not sort to where they are expected. For instance, xyz100 precedes xyz2. In some applications such as listing files, normal order sort may be used where any string of digits in a character string is treated as a single digit with numerical value given by the digit string. For example, the following are in normal order:

XYZ001, XYZ2, XYZ003, XYZ08, XYZ23, XYZ100, XYZQ

We wish to extend normal order sort in two ways:
1. Lower case and upper case letters sort the same (with the upper case value).
2. If a plus (+) or minus (-) sign precedes a digit and does not follow a digit, it is considered part of the following number for sorting purposes.

So 123+456+7890 are three numbers separated by plus signs but A+003 is the same as A3.

To do our sort, we will use a library sort routine but we need to furnish a comparison routine. Write a comparison routine which takes as input two strings of printable, non-space ASCII characters (chr(33)-chr(126)) and returns:

-1 if the first string should precede the second in extended normal order
0 it the two strings are the same in extended normal order, or
1 if the first string should follow the second in extended normal order.

Input

The first line of input contains a single integer N, (1 <= N <= 1000) which is the number of data sets that follow. Each data set consists of a single line of input containing the two strings to be compared separated by a space.

Output

For each data set, you should generate one line of output with the following values: The data set number as a decimal integer (start counting at one), a space and –1, 0 or 1 depending on whether the first string precedes, is the same as, or follows the second string in extended normal order.

Sample Input

5
x-3 X0001
123-456-7890 123+456+7890
xYz000123J XyZ+123j
#$%^&*[]- abcdefgh
Abc47jKL+00123 ABC+47jkL123

Sample Output

1 -1
2 1
3 0
4 -1
5 0

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator