Process Transactions

You are given M bank accounts and N transactions to process. Each account has an initial balance and a minimum balance requirement. For a debit transaction (denoted by T = 1), the transaction is valid only if the account's balance after subtracting the transaction amount V is not less than its minimum required balance. In mathematical terms, a debit transaction is valid if $$B_i - V \geq L_i,$$ where $$B_i$$ is the current balance of account i and $$L_i$$ is its minimum required balance. For a credit transaction (denoted by T = 2), the account's balance is increased by V and the transaction is always valid.

Your task is to simulate the sequence of transactions and output for each whether it is "Valid" or "Invalid".

inputFormat

The input is given from stdin in the following format:

M N
B1 B2 ... BM
L1 L2 ... LM
A1 T1 V1
A2 T2 V2
...
AN TN VN

where:

• M is the number of bank accounts.
• N is the number of transactions.
• B_i are the initial balances of the M accounts.
• L_i are the minimum required balances for the M accounts.
• Each of the following N lines contains three integers: A (the 1-indexed account number), T (the type of transaction, where 1 represents debit and 2 represents credit), and V (the transaction amount).

outputFormat

For each transaction, output a single line to stdout with either "Valid" if the transaction can be processed, or "Invalid" otherwise.## sample

5 4
1000 1500 1200 1300 1100
500 1000 500 1000 500
1 1 600
2 2 300
4 1 1000
5 1 700

Invalid
Valid
Invalid
Invalid