Cheese Trade Record Consistency

On the EJOI continent, a group of farmers started selling cheese at fixed prices. The available coin denominations on EJOI are powers of two, i.e. \(1,2,4,8,\dots\).

At a market, two farmers (say, farmer \(i\) and farmer \(j\)) exchange cheeses. In each transaction, farmer \(i\) initially pays a coin of value \(A\) to \(j\). In some cases, \(j\) also gives change to \(i\) consisting of coins whose denominations are powers of two. The record for each transaction contains four numbers: \(i, j, A, B\). Here, \(A\) is the coin given by \(i\), and \(B\) is interpreted as follows:

• If \(B=-1\) then no change is given by \(j\) (i.e. the cheeses have equal price, so the net exchange is simply \(A\) in value).
• If \(B\neq -1\) then \(B\) represents the smallest coin among those used by \(j\) as change. In this case, if we denote the total value of the coins given in change by \(X\), the transaction is fair provided that the price difference \(\Delta=p_j-p_i\) satisfies \[ \Delta=A-X,\] and since every positive integer has a unique binary representation as a sum of distinct powers of two, the smallest coin in that representation is exactly the lowest set bit of \(X\). That is, when \(B\neq -1\) there exists a positive integer \(X\) with its smallest power-of-two coin equal to \(B\) (i.e. \(X\equiv B\;(\bmod\;2B)\)) and \[ p_j-p_i=A-X.\] Equivalently, the allowed values for \(p_j-p_i\) are numbers of the form \[ A-(B+2Bk)\] for some nonnegative integer \(k\) such that \(B+2Bk\le A\) (and note that when \(B\neq -1,\) it is required that \(A\ge B\)).

The market supervisor recorded all transactions. However, some records might be wrong – that is, they might contradict earlier records about the relative prices of the cheeses. Your task is to process the records in the order given and determine which records are inconsistent with the earlier ones.

Input/Output Explanation: Think of each record as imposing a constraint on the unknown cheese prices \(p_i\) (for all farmers \(i\)). When a record involves two farmers who are already connected (i.e. there is already a derived relation between their prices) then the recorded transaction must agree with the previously deduced difference. Otherwise, if they are not yet connected, you may choose any valid difference (for the case \(B\neq -1\) we choose the one corresponding to \(k=0\), i.e. \(p_j-p_i=A-B\)).

inputFormat

The first line contains a single integer \(n\) (the number of records). Each of the following \(n\) lines contains four integers \(i, j, A, B\), where \(i\) and \(j\) are the farmer identifiers, \(A\) is the coin value paid by farmer \(i\) (a power of two), and \(B\) is either \(-1\) (indicating no change) or a power of two giving the smallest coin among the coins given as change by farmer \(j\).

outputFormat

Output the number of records that are inconsistent with the previously processed records on the first line. Then output the 1-indexed indices of these contradictory records in increasing order (one per line). If there are no contradictions, simply output 0.

sample

5
1 2 8 2
2 3 4 -1
1 3 16 2
2 1 8 -1
3 1 4 1

2
4
5