Interval Usage with Non-Overlapping Overrides

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

You are given a timeline of days ([1..D]) and two kinds of interval events:

Usage intervals: indicate whether a resource is in-use during that period.

Override intervals: override the final state during that period. Override intervals do not overlap each other.

Clarified FastPrep contract

A day is in use by default if at least one usage interval with value 1 covers that day. Usage intervals with value 0 do not clear another usage interval; they simply contribute no usage. Override intervals are the only intervals that force the final state to their value, and override intervals never overlap each other.

Rules:

By default, a day's state is determined by the union/combination of usage intervals.

If a day falls within an override interval, the override value takes precedence over usage.

Implement an algorithm to output the final state for each day from 1 to D.

Input (stdin)

Line 1: integer D.

Line 2: integer U.

Next U lines: l r v describing a usage interval ([l,r]) (inclusive), with v in {0,1}.

Next line: integer O.

Next O lines: l r v describing an override interval ([l,r]) (inclusive), with v in {0,1}. Override intervals never overlap.

Output (stdout)

One line: a string of length D over {'0','1'}, where the i-th char is the final state on day i.

Complexity

Preferably better than day-by-day simulation; e.g. O((U+O) log (U+O) + D).

Example

See tests below.

Example

Input

10

2

1 2 1

4 10 1

1

2 4 0

Output

1000111111

Complete solveIntervalUsageWithOverrides. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.