Distinct Substring Queries 2

Time limit1sMemory limit512 MB

Summary

Process a stream of append-character and count-distinct-substrings queries on a growing string, answering each count query online.

Level: Hard8 of 10
Topics: String, String matching, Sorting, Implementation
Solved: No attempts yet

Problem

There is an empty string $S$ . Write a program that processes the following two kinds of queries in order.

c: append the character c to the end of $S$ . Here c is a lowercase English letter.
?: print the number of distinct substrings of $S$ .

Input

The first line gives a string $Q$ . $Q$ is the concatenation of the queries in the order they are performed. $Q$ consists only of lowercase English letters and ?, and its length does not exceed $200\,000$ . $Q$ contains at least one ?.

Output

For each ?, print the number of distinct substrings of $S$ on its own line.

Examples3

Example 1
Input
```
aba?
```
Expected output
```
5
```
Example 2
Input
```
?z?z?z?
```
Expected output
```
0
1
2
3
```
Example 3
Input
```
abc?abc?
```
Expected output
```
6
15
```