ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1116. Piecewise Constant Function

Time limit: 0.5 second
Memory limit: 64 MB
Problem illustration
SKB Kontur has been developing a new SKB Kontur Framework for the last three months. One of the latest wrinkles is that data will be presented with the help of piecewise constant functions. Your team is to implement an operation of "subsettraction" of the functions. A function is called piecewise constant if its domain can be divided into intervals and the function is constant on each interval. We also assume that the function value at the left-end point of each interval of constancy is equal to its value on the interval. In fig.1 there is a piecewise constant function with three intervals of constancy. Note that the function value at the point B is U and at the points C, E and on the interval (C,D) - the function value is not defined. 
A result of the subsettraction operation of two piecewise constant functions F1 @ F2 is a piecewise constant function F defined as follows:
  • F(x) = F1(x) if F1 is defined and F2 is not defined;
  • F(x) is not defined if F1 and F2 are defined both;
  • F(x) is not defined if F1 is not defined.
In Fig.3 there is the result of the operation of the subsettraction of the two functions from Fig.1 and Fig.2.

Input

contains two lines of the same format. Each line characterizes one piecewise constant function. A line begins with an integer N (1 ≤ N ≤ 15000). Then characterizations of constancy intervals follow in the ascending order with respect to their left ends. Each interval is given by three integer numbers A, B, Y (|A| < 32000, |B| < 32000, |Y| ≤ 100, A < B), where A is the left end of an interval, B is the right end of an interval and Y is the function value on the interval. It's known that that no two intervals from one line intersect. If two intervals are adjacent, the function values on the intervals are different.

Output

contains one line of the same format (see the input specification). This line should describe a result of the operation of subsettraction of the two input piecewise constant functions.

Sample

inputoutput
3 -1 1 2 1 3 4 4 6 3
2 -2 2 1 5 7 5
2 2 3 4 4 5 3
Problem Author: Oleg Kaz
Problem Source: USU Open Collegiate Programming Contest October'2001 Junior Session