题目描述

本题中合法引号串的定义如下：

• "" 是合法引号串。
• 如果 \(A\) 是合法引号串，定义 \(\bar A\) 为同时把 \(A\) 中的 ' 变成 "，把 " 变成 ' 得到的字符串，那么 \(\texttt{"}\bar A\texttt{"}\) （包含引号）是合法引号串。
• 如果 \(A, B\) 均为合法引号串，那么 \(AB\) （字符串拼接）也是合法引号串。

例如：

• "''""" 可以看作 "''" 和 "" 的拼接，因此是合法引号串。
• ""'""'"" 就不是合法引号串。

给出一个长度为 \(n\) 的字符串 \(s\)，保证仅包含 ' 和 "。对于每个下标 \(i\)，计算有多少对 \(1 \le l \le i \le r \le n\) 满足，字符串 \(s_ls_{l+1}\ldots s_r\) 是合法引号串。

输入格式

输入仅一行一个字符串 \(s\)。

保证 \(s\) 仅含 '"，且 \(2 \le |s| \le 10^6\)。

输出格式

输出一行 \(n\) 个整数，空格隔开，行末无空格，其中第 \(i\) 个整数表示下标 \(i\) 的答案。

样例输入

"''"''""''"''"

样例输出

1 1 1 3 2 2 3 3 2 2 3 1 1 1