【题目描述】

Unicode是一种用于编码字符的国际标准，旨在克服ASCII等旧文本编码标准的限制。ASCII和类似系统的主要缺陷在于，它们只表示非常有限的字符数（主要是英语键盘上的字符）。相比之下，Unicode目前编码超过130000个字符（截至2019年），包括来自世界上大多数语言的字符，理论上可以用来表示超过1000000个字符。也许对现代人类通信来说最重要的是，Unicode编码大约3000个表情符号（同样截至2019年）。

Unicode有几种编码“风格”，其中最著名的是UTF-8，每个字符使用8、16、24或32位；UTF-16，每个字符使用16或32位；以及每字符使用32位的UTF-32。在所有这些风格中，字符的编码实际上是对与该字符对应的非负整数的编码；这个整数被称为代码点（不是每个代码点都对应一个字符）。

对于这个问题，我们将重点关注UTF-8。使用UTF-8编码的字符存储在1、2、3或4个字节中，我们将这四个选项分别称为Type1、Type2、Type3和Type4。下表有助于说明这些问题。在每一个字节表示为8位的情况下，最左边的位是最有效的。

Type1–第一个（也是唯一一个）字节以0开头。这个保留7个比特用于存储代码点。

Type2–第一个字节以110开头，第二个字节以10开头。第一字节的剩余5位和第二字节的剩余6位（总共11位）用于存储代码点。

Type3–第一个字节以1110开头，第二个和第三个字节以10开头。第一字节的剩余4位以及第二和第三字节的剩余6位用于存储码点（总共16位）。

Type4–第一个字节以11110开头，第二、第三和第四个字节以10开头。第一字节的剩余3位和第二、第三和第四字节的剩余6位用于存储码点（总共21位）。

如果一个字节序列由一个或多个字符编码组成，每个字符编码都是Type1、Type2、Type3或Type4，则它符合UTF-8标准，在这种情况下，我们认为字节序列是有效的UTF-8。否则，字节序列为无效的UTF-8。例如，在样本输入2中，第一个（也是唯一一个）字节以10开头，但任何UTF-8字符编码的第一个字节中的前两位永远不能是10，因此这是无效的UTF-8。在样本输入3中，第一个字节应该以类型4的字符编码开始，但后面只有两个字节，而不是三个，所以这也是无效的UTF-8。

给定一个字节序列，确定它是否是有效的UTF-8，如果是，则输出Type1、Type2、Type3和Type4的字符编码数。

【输入】

第一行输入包含一个正整数n（1≤n≤1200），即序列中的字节数。后面是n行，按顺序给出n个字节，每行一个。每个字节表示为长度为8的“0”和“1”字符串。每个字节的最左边的位是最高有效位。

【输出】

如果字节序列是无效的UTF-8，则输出“invalid”。否则输出四个整数，每行一个：Type1、Type2、Type3和Type4的字符编码数。

【样本输入1】

6

11100011

10001111

10101010

00000000

11011011

10001110

【样本输出1】

1

1

1

0

【样本输入2】

1

10101010

【样本输出2】

invalid

【样本输入3】

3

11110111

10111111

10111111

【样本输出3】

invalid