CHECKPARENTHESES

#include <bits/stdc++.h>
using namespace std;

int main () {
	int i;
	string s;
	stack<char> check;
	getline(cin, s);
	for (i = 0; i < s.length(); ++i) {
		if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
			check.push(s[i]);
		}
		else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
			if (check.empty())
				break;
			char c = check.top();
			check.pop();
			if (s[i] == ')' && c != '('
				|| s[i] == ']' && c != '['
				|| s[i] == '}' && c != '{') {
				break;
			}
		}
	}
	if (i < s.length() || !check.empty())
		printf("Invalid\n");
	else
		printf("Valid\n");

}