There are N countries exploring a new discovered planet, which is represented as a grid in a Cartesian
plane. At the beginning, each country occupies a separate (non-overlapping) territory. The territory has the
shape of a rectangle whose edges are parallel to the axes Ox and Oy. The territory is determined by four
numbers x1, y1, x2, y2 where (x1, y1) is the coordinate of the bottom left corner and (x2, y2) is the coordinate
of the top right corner of the rectangle (-108 ≤ x1, y1, x2, y2 ≤ 108). Every month, each country expands its
territory to one of four directions: left - the new territory is determined by x1-1, y1, x2, y2; right - the new territory is determined by x1, y1, x2+1, y2; up - the new territory is determined by x1, y1, x2, y2+1; and down - the new territory is determined by x1, y1-1, x2, y2. The conflict happens between two countries when their territories start to overlap each other (the area of the overlapped region is non-zero). Given the plan of
expansion of these countries for the next T months, your task is to write a program to determine after how
many months, the first conflict will happen.
The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.
For each data set, the first line contains two integers N and T (N ≤ 100, T ≤ 100 000). For the ith pair of consecutive lines of the following N pairs of consecutive lines, the first line contains four integers x1, y1, x2, y2 separated by a space determining the initial territory of the ith country; and the second line consists of a string of length T only containing ‘L’, ‘R’, ‘U’, ‘D’ characters describing the plan of expansion of the ith country for the next T months where ‘L’ means left, ‘R’ means right, ‘U’ means up, and ‘D’ means down.
For each data set, write in one line the number of months after which the first conflict will happen, or -1 if no conflict happens.
2 3 6 1 1 2 2 LLURRR 1 3 2 4 LLLLLL 4 1 5 2 LUUUUU 3 10 1 1 2 2 LLLLLLLLLL 1 3 2 4 RRRRRRRRRR 4 1 5 2 DDDDDDDDDD
5 -1
Migrated from old NTUJ.
The ACM-ICPC 2010 Asia Regional Contest, Site Hanoi
| No. | Testdata Range | Score |
|---|