Sequence Transformation via Propagation Operations

We are given two sequences of integers, (A) and (B), each of length (N). We can perform the following two types of operations on (A):

1. Choose a contiguous interval ([a, b]) ((1 \le a \le b \le N)), let (x) be the (\max) element in (A[a \ldots b]), and then replace every element in (A[a \ldots b]) with (x).
2. Choose a contiguous interval ([a, b]) ((1 \le a \le b \le N)), let (x) be the (\min) element in (A[a \ldots b]), and then replace every element in (A[a \ldots b]) with (x).

The task is to convert (A) into (B) using at most (2N) operations. It is guaranteed (or assumed) that (B) is reachable from (A) using these rules. If (B) cannot be obtained, output (-1).

A valid output should first print an integer (K) representing the number of operations, followed by (K) lines. Each line should contain three integers: (a), (b) and an operation type (either (1) for the maximum operation or (2) for the minimum operation), indicating that the operation is to replace all elements in (A[a \ldots b]) with (x) ((x) being either the maximum or the minimum of that interval as defined above).

One common strategy is to process each contiguous block in (B) with equal values. For each block with value (v), if there exists an index in that block where (A[i] = v), then you can propagate (v) to the rest of the segment by performing operations on adjacent intervals. In particular, if a neighbor is less than (v), use operation type 1 (max operation) to propagate; if the neighbor is greater than (v), use operation type 2 (min operation) to propagate. This will ensure that the neighbor will also become (v).

Note: The input indices are 1-indexed.

inputFormat

The first line contains an integer (N) (the length of the sequences).\nThe second line contains (N) space-separated integers representing the sequence (A).\nThe third line contains (N) space-separated integers representing the sequence (B).

outputFormat

If it is impossible to convert (A) to (B) using the allowed operations, print (-1). Otherwise, on the first line print an integer (K), the number of operations (with (K \le 2N)). Then, print (K) lines, each with three integers (a), (b) and (op) (where (op = 1) denotes the maximum replacement operation and (op = 2) denotes the minimum replacement operation). The operations should transform (A) into (B).

sample

5
4 2 3 1 5
4 4 4 1 5

2
1 2 1
2 3 1