Taco Pyramid Validation

This problem asks you to determine whether a given sequence of words forms a valid pyramid. A pyramid means that each successive word in the sequence is constructed by appending exactly one character to the previous word, and furthermore, the previous word must be a prefix of the current one. In mathematical terms, if the sequence contains \(n\) words \(w_1, w_2, \ldots, w_n\), then for every \(i\) from 2 to \(n\), it must hold that \(|w_i| = |w_{i-1}| + 1\) and \(w_{i-1}\) is a prefix of \(w_i\). Your task is to verify whether the given sequence satisfies these conditions.

inputFormat

The input consists of multiple test cases. Each test case starts with an integer \(n\) (with \(n \ge 1\)) specifying the number of words, followed by \(n\) lines each containing one word. The input is terminated by a test case where \(n = 0\), which should not be processed.

outputFormat

For each test case, output a single line containing either "valid" if the sequence of words forms a valid pyramid or "invalid" otherwise.

3
a
ab
abc
0

valid