Call Forwarding

Thanks to computer technology the functionality of phone systems has been greatly enhanced in the last ten years. We have automated menus, sophisticated answering machines, conference call capabilities, group addressing and so on. A common feature of a company's phone system is the ability to set call forwarding. For example, if Bob at the Nobody's Home Company (NHC) goes on vacation, he sets things up so that all calls coming to him are forwarded to his associate Jane. This problem addresses how phone systems might keep track of call forwarding.

The phones at the NHC all have four digit extensions. Employees can set call forwarding by entering the appropriate information through their telephone interface. If an employee is going to be away they enter the following information: their extension, the time they are leaving, how long they will be away, and the extension that their calls should be forwarded to, with the following constraints:

• All extensions consist of four digits.
• The extensions 0000 and 9999 are reserved for special use and will not be entered as information by an employee.
• Times are recorded in increments of 1 hour and are based on a clock that begins at 0000 at midnight every New Year's Eve. Therefore, when describing the time they are leaving, employees always use an integer between 0000 and 8784 (which is 366*24). The call forwarding system is completely reset at the beginning of the year.
• A call forward set to start at time X for a duration of Y will be in effect from time X to time X+Y inclusive.

Users are ``good" about the requests they enter. They follow the format rules. They do not enter a request such that the duration of the request would go past the end of the year. They do not enter two requests for their extension that overlap in time. Even though the users enter correct, clear, non-overlapping information from their own point of view, a degenerate situation can still occur in a call forwarding system, if requests have been made in such a way as to forward a call back to the original target of the call. For example if Bob forwards his calls to Sue, and Sue forwards her calls to Joe, and Joe forwards his calls to Bob then when somebody calls any of these three people their calls would be forwarded forever. To prevent this situation the call forwarding system uses the ``dead end" number 9999. Any calls made to an extension involved in such a degenerate situation will be forwarded to the special 9999 extension.

Input

The first line contains an integer N between 1 and 10 describing how many call forwarding systems will be simulated by your program. Each call forwarding system will be represented by 0 to 100 `source time duration target' lines. These lines represent the requests by the users to set up a call forwarding from the `source' to the `target' starting at the `time' for a length of `duration', and will be in the form `dddd dddd dddd dddd'. A line with 0000 in the `source' position indicates the end of this portion of the input. The call forwarding requests are listed in the order received. They will be followed by 1 or more `time extension' lines, in the form `dddd dddd', in non-decreasing order by `time' representing calls made into the system at `time' to `extension'. A line with 9000 in the `time' position indicates the end of this portion of the input.

Output

The first line of output must read CALL FORWARDING OUTPUT. This will be followed by sections of information about each of the call forwarding systems being simulated. Each of these sections should be headed by the line SYSTEM N, where N is the number (1, 2, ...) of the system. Within the section there should be a line describing the result of each of the calls made into the system, with the format ``AT dddd CALL TO dddd RINGS dddd". The final line of output should read END OF OUTPUT.

Sample Input

2
1111 0100 0200 2222
1111 0301 0500 4444
2222 0200 0200 3333
3333 0250 1000 1111
7777 1000 2000 7777
0000
0050 1111
0150 1111
0200 1111
0225 2222
0270 1111
0320 1111
0320 3333
0900 3000
1250 3333
1250 7777
9000
0000
3000 1111
9000

Sample Output

CALL FORWARDING OUTPUT
SYSTEM 1
AT 0050 CALL TO 1111 RINGS 1111
AT 0150 CALL TO 1111 RINGS 2222
AT 0200 CALL TO 1111 RINGS 3333
AT 0225 CALL TO 2222 RINGS 3333
AT 0270 CALL TO 1111 RINGS 9999
AT 0320 CALL TO 1111 RINGS 4444
AT 0320 CALL TO 3333 RINGS 4444
AT 0900 CALL TO 3000 RINGS 3000
AT 1250 CALL TO 3333 RINGS 1111
AT 1250 CALL TO 7777 RINGS 9999
SYSTEM 2
AT 3000 CALL TO 1111 RINGS 1111
END OF OUTPUT

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
struct E {
    int time, duration, target;
    E(int a, int b, int c):
        time(a), duration(b), target(c) {}
};
vector<E> g[10000];
int called[10000];
int RING(int source, int time) {
    called[source] = 1;
    int i;
    for(i = 0; i < g[source].size(); i++) {
        if(g[source][i].time <= time && time <= g[source][i].time+g[source][i].duration) {
            if(called[g[source][i].target])
                return 9999;
            return RING(g[source][i].target, time);
        }
    }
    return source;
}
int main() {
    int testcase = 0, cases = 0;
    scanf("%d", &testcase);
    puts("CALL FORWARDING OUTPUT");
    while(testcase--) {
        printf("SYSTEM %d\n", ++cases);
        int i, j, k;
        for(i = 0; i < 10000; i++)
            g[i].clear();
        int source, time, duration, target;
        while(scanf("%d", &source) == 1 && source) {
            scanf("%d %d %d", &time, &duration, &target);
            g[source].push_back(E(time, duration, target));
        }
        while(scanf("%d", &time) == 1 && time != 9000) {
            scanf("%d", &source);
            memset(called, 0, sizeof(called));
            printf("AT %04d CALL TO %04d RINGS %04d\n", time, source, RING(source, time));
        }
    }
    puts("END OF OUTPUT");
    return 0;
}