// Arup Guha
// 10/24/2015
// Solution to 2000 UCF HS Contest Problem: Acknowledged

import java.util.*;

public class ackl {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		String transaction = stdin.next();
		int loop = 1;

		// Process each case.
		while (!transaction.equals("EOF")) {

			// Initial settings for empty log.
			boolean valid = true;
			boolean[] items = new boolean[2];

			// Just process this case.
			while (!transaction.equals("EOT")) {

				// Parse out info.
				int num = Integer.parseInt(transaction.substring(1))-1;
				char type = transaction.charAt(0);

				// Message...
				if (type == 'm') {

					// Just one.
					if (num < 10) {
						if (items[num]) valid = false;
						else items[num] = true;
					}

					// Just do both.
					else {
						if (items[0] || items[1]) valid = false;
						else {
							items[0] = true;
							items[1] = true;
						}
					}
				}

				// Acknowledge step.
				else {

					// Just one.
					if (num < 10) {
						if (!items[num]) valid = false;
						else items[num] = false;
					}

					// Just do both.
					else {
						if (!items[0] || !items[1]) valid = false;
						else {
							items[0] = false;
							items[1] = false;
						}
					}
				}

				// Get next transaction for this session.
				transaction = stdin.next();
			}

			// Print out the result - everything must be acknowledged...
			if (valid && !items[0] && !items[1])
				System.out.println("Transaction "+loop+": valid\n");
			else
				System.out.println("Transaction "+loop+": invalid\n");

			// Go to the next step.
			transaction = stdin.next();
			loop++;
		}
	}
}