E - Forbidden Prefix
Source: atcoder
Difficulty: 500

Problem Statement
There are two multisets of strings,
X
and
Y
, both initially empty.
You are given
Q
queries to process in order. In the
i
-th query, you receive an integer
T_i
and a string
S_i
. If
T_i=1
, insert
S_i
into
X
; if
T_i=2
, insert
S_i
into
Y
.
After processing each query, print this value:
the number of strings in
Y
that have no element of
X
as a prefix.
Constraints
Q
is an integer between
1
and
2 \times 10^5
, inclusive.
T_i \in \{1,2\}
Each
S_i
is a string of length between
1
and
5\times 10^5
, inclusive, consisting of lowercase English letters.
\displaystyle \sum_{i=1}^Q |S_i| \leq 5 \times 10^5
Input
The input is given from Standard Input in the following format:
Q
T_1\ S_1
T_2\ S_2
\vdots
T_Q\ S_Q
Output
Print
Q
lines. The
i
-th line
(1 \leq i \leq Q)
should contain the count after processing the
i
-th query.
Sample Input 1
4
1 at
2 watcoder
2 atcoder
1 wa
Sample Output 1
0
1
1
0
The counts after processing the queries for
i=1,2,3,4
are as follows.
i=1
:
Y
is empty, so the count is
0
.
i=2
:
watcoder
has no element of
X
as a prefix, so the count is
1
.
i=3
:
watcoder
has no element of
X
as a prefix, while
atcoder
has
at
as a prefix, so the count is
1
.
i=4
:
watcoder
has
wa
as a prefix, and
atcoder
has
at
as a prefix, so the count is
0
.
Sample Input 2
10
1 w
1 avko
2 atcoder
1 bzginn
2 beginner
1 atco
2 contest
1 ntxcdg
1 atc
1 contest
Sample Output 2
0
0
1
1
2
1
2
2
2
1

C++ solution:
#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define SZ(s) (int)s.size()
#define ff first
#define ss second

const int N = (5e5 + 5);

string s;

int ans, a[N], b[N], k, v[N][26];

char c[N];

void f(int x, int y) {
    ans -= a[x];
    for(int i = 0; i < 26; i++) {
        if(v[x][i] and !b[v[x][i]]) f(v[x][i], x);
    }
}

void dfs(int x, int y, int ind, int t) {
    if(t == 1) {
        if(ind == SZ(s)) {
            f(x, y);
            b[x] = true;
            return;
        }
        if(v[x][s[ind]-'a']) {
            if(b[v[x][s[ind]-'a']]) return;
            dfs(v[x][s[ind]-'a'], x, ind+1, t);
            return;
        }
        v[x][s[ind]-'a'] = (++k);
        c[k] = s[ind];
        dfs(k, x, ind+1, t);
        return;
    }
    if(ind == SZ(s)) {
        a[x]++;
        ans++;
        return;
    }
    if(v[x][s[ind]-'a'] and b[v[x][s[ind]-'a']]) return;
    if(v[x][s[ind]-'a']) {
        dfs(v[x][s[ind]-'a'], x, ind+1, t);
        return;
    }
    if(!v[x][s[ind]-'a']) {
        v[x][s[ind]-'a'] = (++k);
        c[k] = s[ind];
        dfs(k, x, ind+1, t);
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int q;
    cin >> q;
    while(q--) {
        int t;
        cin >> t >> s;
        dfs(0, -1, 0, t);
        cout << ans << "\n";
    }

    return 0;
}

Go solution:
// Code generated by Gottani; see https://github.com/ktateish/gottani/. DO NOT EDIT.
package main

import (
	"bufio"
	"fmt"
	"strings"

	"io"
	"os"
	"sort"
	"strconv"
)

//line github.com/ywak/atcoder/lib/ds/trie.go:8
type Trie struct {
	root *TrieNode
}

type TrieNode struct {
	end  int
	prev *TrieNode
	next map[byte]*TrieNode
}

func NewTrie() *Trie {
	trie := &Trie{}
	trie.root = trie.newNode(nil)

	return trie
}

func (t *Trie) newNode(parent *TrieNode) *TrieNode {
	return &TrieNode{
		end:  0,
		prev: parent,
		next: map[byte]*TrieNode{},
	}
}

func (t *Trie) Insert(s []byte) {
	node := t.root
	for _, c := range s {
		// idx := t.indexOf(c)
		next := node.next[c]
		if next == nil {
			next = t.newNode(node)
			node.next[c] = next
		}

		node = next
	}
	node.end++
}

func (t *Trie) findPrefixNode(s []byte) *TrieNode {
	node := t.root
	for _, c := range s {
		if node == nil {
			return nil
		}
		node = node.next[c]
	}
	return node
}

func (t *Trie) RemovePrefix(s []byte) int {
	node := t.findPrefixNode(s)
	if node == nil {
		return 0
	}
	delete(node.prev.next, s[len(s)-1])

	// このノードから、各ノードを削除していく。
	count := 0
	queue := []*TrieNode{node}
	for len(queue) > 0 {
		node = queue[0]
		queue = queue[1:]
		count += node.end
		for _, next := range node.next {
			queue = append(queue, next)
		}
	}

	return count
}

func (t *Trie) IsPrefixOf(s []byte) bool {
	node := t.root
	for _, c := range s {
		// prefixとしてたどり終わったので、解決とする
		if node.end > 0 {
			break
		}

		// 次のノードがない場合、絶対にprefixではない
		next := node.next[c]
		if next == nil {
			return false
		}
		node = next
	}
	return node.end > 0
}

func (t *Trie) String() string {
	strs := []string{}
	var dfs func(node *TrieNode, prefix string)
	dfs = func(node *TrieNode, prefix string) {
		if node == nil {
			return
		}
		suffix := ""
		if node.end > 0 {
			suffix = "*"
		}
		strs = append(strs, fmt.Sprintf("\"%s\"%s", prefix, suffix))
		for c, next := range node.next {
			dfs(next, fmt.Sprintf("%s%c", prefix, c))
		}
	}
	dfs(t.root, "")

	return strings.Join(strs, ", ")
}

//line github.com/ywak/atcoder/lib/io/io.go:16
type In struct {
	// NextString は 次の入力を文字列として読み込んで返します。
	NextString func() string
}

type Out struct {
	writer io.Writer
	Flush  func()
}

type InitIoProps struct {
	// バッファを行うかどうか。
	DoBuffer bool

	// 行単位で読むか、改行単位で読むか。
	ReadLine bool
}

func InitIo(props *InitIoProps) (*In, *Out) {
	bufsize := 4 * 1024 * 1024 // 4MB

	// 入力はずっとバッファーでいいらしい。ほんとう？
	// TODO バッファなしfmt.Fscanf(os.Stdin)だとTLEだった。要調査
	_in := bufio.NewScanner(os.Stdin)
	if !props.ReadLine {
		_in.Split(bufio.ScanWords)
	}
	_in.Buffer(make([]byte, bufsize), bufsize)
	in := func() string {
		_in.Scan()
		return _in.Text()
	}

	// 出力はバッファon/offが必要
	var out io.Writer
	var flush func()

	if props.DoBuffer {
		_out := bufio.NewWriterSize(os.Stdout, bufsize)
		out = _out
		flush = func() {
			_out.Flush()
		}
	} else {
		out = os.Stdout
		flush = func() {}
	}

	return &In{in}, &Out{out, flush}
}

// NextBytes は 次の入力をbyteの配列として読み込んで返します。
// 遅いから極力使わない。
func (in *In) NextBytes() []byte {
	return []byte(in.NextString())
}

// NextInt は 次の入力を数値として読み込んで返します。
func (in *In) NextInt() int {
	i, _ := strconv.Atoi(in.NextString())
	return i
}

// NextInt2 は 次の2つの入力を数値として読み込んで返します。
func (in *In) NextInt2() (int, int) {
	return in.NextInt(), in.NextInt()
}

// NextInt2d は 次の2つの入力を数値n1,n2として読み込んで、n1+d1, n2+d2を返します。
func (in *In) NextInt2d(d1, d2 int) (int, int) {
	return in.NextInt() + d1, in.NextInt() + d2
}

// NextInt3 は 次の3つの入力を数値として読み込んで返します。
func (in *In) NextInt3() (int, int, int) {
	return in.NextInt(), in.NextInt(), in.NextInt()
}

// NextInt2d は 次の3つの入力を数値n1,n2,n3として読み込んで、n1+d1, n2+d2, n3+d3を返します。
func (in *In) NextInt3d(d1, d2, d3 int) (int, int, int) {
	return in.NextInt() + d1, in.NextInt() + d2, in.NextInt() + d3
}

// NextInt4 は 次の4つの入力を数値として読み込んで返します。
func (in *In) NextInt4() (int, int, int, int) {
	return in.NextInt(), in.NextInt(), in.NextInt(), in.NextInt()
}

// NextInts は 次のn個の入力を数値として読み込んで、配列として返します。
func (in *In) NextInts(n int) sort.IntSlice {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = in.NextInt()
	}
	return sort.IntSlice(a)
}

// NextLongIntAsArray は 次の入力を数値として読み込み、各桁を要素とした配列を返します。
func (in *In) NextLongIntAsArray() []int {
	s := in.NextString()
	l := len(s)
	arr := make([]int, l)
	for i := 0; i < l; i++ {
		arr[i] = int(s[i] - '0')
	}

	return arr
}

// NextBytesOffsetは、次の入力を文字列として読み込み、各文字cについて(c-offset)に置き換えた配列を返します。
func (in *In) NextBytesOffset(offset byte) []int {
	s := in.NextString()
	arr := make([]int, len(s))
	for i, v := range s {
		arr[i] = int(byte(v) - offset)
	}
	return arr
}

// NextFloat は 次の入力を実数値として読み込み、値を返します。
func (in *In) NextFloat() float64 {
	f, _ := strconv.ParseFloat(in.NextString(), 64)
	return f
}

// Println は引数をスペース区切りで出力し、最後に改行を出力します。
func (out *Out) Println(a ...interface{}) {
	fmt.Fprintln(out.writer, a...)
}

// Printf はformatにしたがってaを整形して出力します。
func (out *Out) Printf(format string, a ...interface{}) {
	fmt.Fprintf(out.writer, format, a...)
}

// PrintStringsln は文字列配列の各要素をスペース区切りで出力し、最後に改行を出力します。
func (out *Out) PrintStringsln(a []string) {
	out.Println(strings.Join(a, " "))
}

// PrintIntsLn は整数配列の各要素をスペース区切りで出力し、最後に改行を出力します。
func (out *Out) PrintIntsLn(a []int) {
	b := make([]string, len(a))
	for i, v := range a {
		b[i] = fmt.Sprint(v)
	}
	out.Println(strings.Join(b, " "))
}

func (out *Out) PrintLenAndIntsLn(a []int) {
	b := make([]string, len(a)+1)
	b[0] = fmt.Sprint(len(a))
	for i, v := range a {
		b[i+1] = fmt.Sprint(v)
	}
	out.Println(strings.Join(b, " "))
}

// Putcは一文字出力します。
func (out *Out) Putc(c byte) {
	out.Printf("%c", c)
}

// YesNo は condが真ならYes, 偽ならNoを出力します。
func (out *Out) YesNo(cond bool) {
	if cond {
		out.Println("Yes")
	} else {
		out.Println("No")
	}
}

func (out *Out) YESNO(cond bool) {
	if cond {
		out.Println("YES")
	} else {
		out.Println("NO")
	}
}

//line main.go:16
func calc(in *In, out *Out) {
	Q := in.NextInt()

	// prefixの集合
	x_root := NewTrie()

	//
	y_root := NewTrie()

	ans := 0
	for q := 0; q < Q; q++ {
		t := in.NextInt()
		s := in.NextBytes()

		switch t {
		case 1:
			// prefixが追加されたので、ここで除外されるような文字列を削除する
			x_root.Insert(s)
			ans -= y_root.RemovePrefix(s)
		case 2:
			// 既に対応するprefixが存在するなら、無視してよい
			// そうでないなら、文字列を記録しておき、あとで対応する
			if !x_root.IsPrefixOf(s) {
				y_root.Insert(s)
				ans++
			}
		}
		out.Println(ans)
	}
}

func main() {
	in, out := InitIo(&InitIoProps{
		DoBuffer: true, // インタラクティブならfalseにすること。
		ReadLine: false,
	})
	defer out.Flush()

	calc(in, out)
}

Java solution:
import java.io.*;
import java.math.*;
import java.util.*;
import java.util.function.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	private static void solve(final FastScanner sc, final FastPrinter out) {
		int q = sc.nextInt();
		Trie x = new Trie('a', 26);
		Trie y = new Trie('a', 26);
		while (q-- > 0) {
			int t = sc.nextInt();
			if (t == 1) {
				String word = sc.next();
				x.insert(word);
				y.removePrefix(word);
			} else {
				String word = sc.next();
				if (!x.hasPrefix(word)) {
					y.insert(word);
				}
			}
			out.println(y.totalWords());
		}
	}

	public static void main(String[] args) {
		try (final FastScanner sc = new FastScanner();
			 final FastPrinter out = new FastPrinter()) {
			solve(sc, out);
		} catch (Exception e) {
			throw new RuntimeException(e);
		}
	}

	@SuppressWarnings("unused")
	private static final class Trie {
		/**
		 * このノードのラベルとなる文字
		 */
		private final char label;

		/**
		 * インデックス計算の基準となる文字番号
		 */
		private final int baseCodePoint;

		/**
		 * 基準文字からの有効文字数
		 */
		private final int charSize;

		/**
		 * 子ノードの配列
		 */
		private Trie[] childNodes;

		/**
		 * このノードに挿入された文字列の総数
		 */
		private int totalWords;

		/**
		 * このTrieに登録された文字数
		 */
		private int uniqueWordCount;

		/**
		 * このノードを終点とする文字の総数
		 */
		private int terminalCount;

		/**
		 * ノードの終端に文字列を保存
		 */
		private String word;

		/**
		 * デフォルトの設定で初期化します。
		 */
		public Trie() {
			this('A', 'z' - 'A' + 1);
		}

		/**
		 * 基準文字と、有効文字数を指定し、初期化します。
		 *
		 * @param baseCodePoint 基準文字
		 * @param charSize      有効文字数
		 */
		public Trie(final int baseCodePoint, final int charSize) {
			this.baseCodePoint = baseCodePoint;
			this.charSize = charSize;
			childNodes = new Trie[charSize];
			uniqueWordCount = totalWords = terminalCount = label = 0;
		}

		/**
		 * 新しいノードを作成する用の内部コンストラクタ
		 *
		 * @param label このノードの文字
		 */
		private Trie(char label, int baseCodePoint, int charSize) {
			this.baseCodePoint = baseCodePoint;
			this.charSize = charSize;
			this.label = label;
			childNodes = new Trie[charSize];
		}

		/**
		 * 文字からインデックスを計算します。
		 *
		 * @param c 文字
		 * @return インデックス
		 */
		private int charToIndex(final char c) {
			return c - baseCodePoint;
		}

		/**
		 * このTrieに文字列を追加します。
		 *
		 * @param word 追加する文字列
		 * @return 追加した文字の総数
		 */
		public int insert(final String word) {
			if (word == null || word.isBlank()) return 0;
			return insert(word, 0);
		}

		/**
		 * insertメソッドの内部メソッド
		 *
		 * @param word  文字列
		 * @param index 読み込んだ文字の番号
		 * @return 追加した文字の総数
		 */
		private int insert(final String word, final int index) {
			totalWords++;
			char currentChar = word.charAt(index);
			int charIndex = charToIndex(currentChar);
			Trie child = childNodes[charIndex];
			if (child == null) child = childNodes[charIndex] = new Trie(currentChar, baseCodePoint, charSize);
			if (word.length() - 1 == index) {
				child.terminalCount++;
				child.totalWords++;
				boolean firstInsertion = child.terminalCount == 1;
				if (firstInsertion) {
					child.uniqueWordCount++;
					child.word = word;
					uniqueWordCount++;
				}
				return child.terminalCount;
			}
			int endCount = child.insert(word, index + 1);
			if (endCount == 1) uniqueWordCount++;
			return endCount;
		}

		/**
		 * このTrieに指定の文字列が登録されているか判定します。
		 *
		 * @param word 判定する文字列
		 * @return 登録されているなら true, そうでなければ false
		 */
		public boolean contains(final String word) {
			if (word == null || word.isBlank()) return false;
			return contains(word, 0);
		}

		/**
		 * containsメソッドの内部メソッド
		 *
		 * @param word  文字列
		 * @param index 読み込んだ文字の番号
		 * @return 登録されているなら true, そうでなければ false
		 */
		private boolean contains(final String word, final int index) {
			char c = word.charAt(index);
			int i = charToIndex(c);
			Trie child = childNodes[i];
			if (child == null) return false;
			if (word.length() - 1 == index) return child.terminalCount > 0;
			return child.contains(word, index + 1);
		}

		/**
		 * このTrieに登録されている文字列を削除します。
		 *
		 * @param word 削除する文字列
		 * @return 削除した文字の総数
		 */
		public int remove(final String word) {
			if (word == null || word.isBlank()) return 0;
			return remove(word, 0);
		}

		/**
		 * removeメソッドの内部メソッド
		 *
		 * @param word  文字列
		 * @param index 読み込んだ文字の番号
		 * @return 削除した文字の総数
		 */
		private int remove(String word, int index) {
			char c = word.charAt(index);
			int i = charToIndex(c);
			Trie child = childNodes[i];
			if (child == null) return 0;
			if (word.length() - 1 == index) {
				int endCount = child.terminalCount;
				if (child.totalWords == endCount) {
					childNodes[i] = null;
				} else {
					child.uniqueWordCount--;
					child.word = null;
					child.terminalCount = 0;
					child.totalWords -= endCount;
				}
				return endCount;
			}
			int rmCnt = child.remove(word, index + 1);
			if (rmCnt == 0) return 0;
			if (rmCnt == totalWords) childNodes[i] = null;
			uniqueWordCount--;
			totalWords -= rmCnt;
			return rmCnt;
		}

		/**
		 * このTrieに登録されている文字列を取得します。
		 *
		 * @return 登録されている文字列
		 */
		public boolean hasPrefix(final String word) {
			if (word == null || word.isBlank()) return false;
			return hasPrefix(word, 0);
		}

		/**
		 * hasPrefixメソッドの内部メソッド
		 *
		 * @param word  文字列
		 * @param index 読み込んだ文字の番号
		 * @return 登録されているなら true, そうでなければ false
		 */
		private boolean hasPrefix(final String word, final int index) {
			char c = word.charAt(index);
			int i = charToIndex(c);
			Trie child = childNodes[i];
			if (child == null) return false;
			if (child.terminalCount > 0) return true;
			if (word.length() - 1 == index) return false;
			return child.hasPrefix(word, index + 1);
		}

		/**
		 * このTrieに登録されている文字列の接頭辞の数を取得します。
		 *
		 * @param prefix 接頭辞
		 * @return 接頭辞の数
		 */
		public int countPrefix(final String prefix) {
			if (prefix == null || prefix.isBlank()) return 0;
			return countPrefix(prefix, 0);
		}

		/**
		 * countPrefixメソッドの内部メソッド
		 *
		 * @param prefix 接頭辞
		 * @param index  読み込んだ文字の番号
		 * @return 接頭辞の数
		 */
		private int countPrefix(final String prefix, int index) {
			char c = prefix.charAt(index);
			int i = charToIndex(c);
			Trie child = childNodes[i];
			if (child == null) return 0;
			if (word.length() - 1 == index) return child.uniqueWordCount;
			return child.countPrefix(prefix, index + 1);
		}

		/**
		 * このTrieに登録されている文字列の数を取得します。
		 *
		 * @param word 文字列
		 * @return 登録されている文字列の数
		 */
		public int count(final String word) {
			if (word == null || word.isBlank()) return 0;
			return count(word, 0);
		}

		/**
		 * countメソッドの内部メソッド
		 *
		 * @param word  文字列
		 * @param index 読み込んだ文字の番号
		 * @return 登録されているなら true, そうでなければ false
		 */
		private int count(final String word, int index) {
			char c = word.charAt(index);
			int i = charToIndex(c);
			Trie child = childNodes[i];
			if (child == null) return 0;
			if (this.word.length() - 1 == index) return child.terminalCount;
			return child.count(word, index + 1);
		}

		/**
		 * このTrieに登録されている文字列の接頭辞を削除します。
		 *
		 * @param word 接頭辞
		 * @return 削除した文字の総数
		 */
		public int removePrefix(final String word) {
			if (word == null || word.isBlank()) return 0;
			int[] rmCnt = new int[2];
			removePrefix(word, 0, rmCnt);
			return rmCnt[0];
		}

		/**
		 * removePrefixメソッドの内部メソッド
		 *
		 * @param word  文字列
		 * @param index 読み込んだ文字の番号
		 * @param rmCnt 削除した文字の総数
		 */
		private void removePrefix(String word, int index, int[] rmCnt) {
			char c = word.charAt(index);
			int i = charToIndex(c);
			Trie child = childNodes[i];
			if (child == null) return;
			if (word.length() - 1 == index) {
				childNodes[i] = null;
				uniqueWordCount -= child.uniqueWordCount;
				totalWords -= child.totalWords;
				rmCnt[0] = child.uniqueWordCount;
				rmCnt[1] = child.totalWords;
				return;
			}
			child.removePrefix(word, index + 1, rmCnt);
			if (rmCnt[1] == 0) return;
			if (rmCnt[1] == totalWords) {
				childNodes[i] = null;
			}
			uniqueWordCount -= rmCnt[0];
			totalWords -= rmCnt[1];
		}

		/**
		 * このTrieに登録されている文字列の数を取得します。
		 *
		 * @return 登録されている文字列の数
		 */
		public int size() {
			return uniqueWordCount;
		}

		/**
		 * このTrieに追加した文字列の総数を取得します。
		 *
		 * @return 追加した文字列の総数
		 */
		public int totalWords() {
			return totalWords;
		}

		/**
		 * このTrieをクリアします。
		 */
		public void clear() {
			uniqueWordCount = totalWords = 0;
			childNodes = new Trie[charSize];
		}
	}

	@SuppressWarnings("unused")
	private static final class FastScanner implements AutoCloseable {
		private static final int DEFAULT_BUFFER_SIZE = 65536;
		private final InputStream in;
		private final byte[] buffer;
		private int pos = 0, bufferLength = 0;

		public FastScanner() {
			this(System.in, DEFAULT_BUFFER_SIZE);
		}

		public FastScanner(final InputStream in) {
			this(in, DEFAULT_BUFFER_SIZE);
		}

		public FastScanner(final int bufferSize) {
			this(System.in, bufferSize);
		}

		public FastScanner(final InputStream in, final int bufferSize) {
			this.in = in;
			this.buffer = new byte[bufferSize];
		}

		private static boolean isWhitespace(final int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t';
		}

		@Override
		public void close() throws IOException {
			if (in != System.in)
				in.close();
		}

		public byte read() {
			if (pos >= bufferLength) {
				try {
					bufferLength = in.read(buffer, pos = 0, buffer.length);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				if (bufferLength < 0)
					throw new RuntimeException(new IOException("End of input reached"));
			}
			return buffer[pos++];
		}

		public int nextInt() {
			int b = read();
			while (isWhitespace(b)) b = read();
			boolean negative = b == '-';
			if (negative) b = read();
			int result = 0;
			while ('0' <= b && b <= '9') {
				result = result * 10 + b - '0';
				b = read();
			}
			return negative ? -result : result;
		}

		public long nextLong() {
			int b = read();
			while (isWhitespace(b)) b = read();
			boolean negative = b == '-';
			if (negative) b = read();
			long result = 0;
			while ('0' <= b && b <= '9') {
				result = result * 10 + b - '0';
				b = read();
			}
			return negative ? -result : result;
		}

		public double nextDouble() {
			int b = read();
			while (isWhitespace(b)) b = read();
			boolean negative = b == '-';
			if (negative) b = read();
			double result = 0;
			while ('0' <= b && b <= '9') {
				result = result * 10 + b - '0';
				b = read();
			}
			if (b == '.') {
				b = read();
				double factor = 10;
				while ('0' <= b && b <= '9') {
					result += (b - '0') / factor;
					factor *= 10;
					b = read();
				}
			}
			return negative ? -result : result;
		}

		public char nextChar() {
			byte b = read();
			while (isWhitespace(b)) b = read();
			return (char) b;
		}

		public String next() {
			return nextStringBuilder().toString();
		}

		public StringBuilder nextStringBuilder() {
			StringBuilder sb = new StringBuilder();
			byte b = read();
			while (isWhitespace(b)) b = read();
			while (!isWhitespace(b)) {
				sb.appendCodePoint(b);
				b = read();
			}
			return sb;
		}

		public String nextLine() {
			StringBuilder sb = new StringBuilder();
			int b = read();
			while (b != 0 && b != '\r' && b != '\n') {
				sb.appendCodePoint(b);
				b = read();
			}
			return sb.toString();
		}

		public BigInteger nextBigInteger() {
			return new BigInteger(next());
		}

		public BigDecimal nextBigDecimal() {
			return new BigDecimal(next());
		}

		public int[] nextInt(final int n) {
			final int[] a = new int[n];
			setAll(a, i -> nextInt());
			return a;
		}

		public long[] nextLong(final int n) {
			final long[] a = new long[n];
			setAll(a, i -> nextLong());
			return a;
		}

		public double[] nextDouble(final int n) {
			final double[] a = new double[n];
			setAll(a, i -> nextDouble());
			return a;
		}

		public char[] nextChars() {
			return next().toCharArray();
		}

		public char[] nextChars(final int n) {
			final char[] c = new char[n];
			for (int i = 0; i < n; i++)
				c[i] = nextChar();
			return c;
		}

		public String[] nextStrings(final int n) {
			final String[] s = new String[n];
			setAll(s, i -> next());
			return s;
		}

		public int[][] nextIntMat(final int h, final int w) {
			final int[][] a = new int[h][w];
			for (int i = 0; i < h; i++)
				setAll(a[i], j -> nextInt());
			return a;
		}

		public long[][] nextLongMat(final int h, final int w) {
			final long[][] a = new long[h][w];
			for (int i = 0; i < h; i++)
				setAll(a[i], j -> nextLong());
			return a;
		}

		public double[][] nextDoubleMat(final int h, final int w) {
			final double[][] a = new double[h][w];
			for (int i = 0; i < h; i++)
				setAll(a[i], j -> nextDouble());
			return a;
		}

		public char[][] nextCharMat(final int n) {
			final char[][] c = new char[n][];
			setAll(c, j -> nextChars());
			return c;
		}

		public char[][] nextCharMat(final int h, final int w) {
			final char[][] c = new char[h][w];
			for (int i = 0; i < h; i++)
				for (int j = 0; j < w; j++)
					c[i][j] = nextChar();
			return c;
		}

		public String[][] nextStringMat(final int h, final int w) {
			final String[][] s = new String[h][w];
			for (int i = 0; i < h; i++)
				setAll(s[i], j -> next());
			return s;
		}

		public int[][][] nextInt3D(final int x, final int y, final int z) {
			final int[][][] a = new int[x][y][z];
			for (int i = 0; i < x; i++)
				for (int j = 0; j < y; j++)
					for (int k = 0; k < z; k++)
						a[i][j][k] = nextInt();
			return a;
		}

		public long[][][] nextLong3D(final int x, final int y, final int z) {
			final long[][][] a = new long[x][y][z];
			for (int i = 0; i < x; i++)
				for (int j = 0; j < y; j++)
					for (int k = 0; k < z; k++)
						a[i][j][k] = nextLong();
			return a;
		}

		public int[] nextSortedInt(final int n) {
			final int[] a = nextInt(n);
			sort(a);
			return a;
		}

		public long[] nextSortedLong(final int n) {
			final long[] a = nextLong(n);
			sort(a);
			return a;
		}

		public double[] nextSortedDouble(final int n) {
			final double[] a = nextDouble(n);
			sort(a);
			return a;
		}

		public char[] nextSortedChars() {
			final char[] c = nextChars();
			sort(c);
			return c;
		}

		public char[] nextSortedChars(final int n) {
			final char[] c = nextChars(n);
			sort(c);
			return c;
		}

		public String[] nextSortedStrings(final int n) {
			final String[] s = nextStrings(n);
			sort(s);
			return s;
		}

		public int[] nextIntPrefixSum(final int n) {
			final int[] ps = new int[n];
			setAll(ps, i -> i > 0 ? nextInt() + ps[i - 1] : nextInt());
			return ps;
		}

		public long[] nextLongPrefixSum(final int n) {
			final long[] ps = new long[n];
			setAll(ps, i -> i > 0 ? nextLong() + ps[i - 1] : nextLong());
			return ps;
		}

		public int[][] nextIntPrefixSum(final int h, final int w) {
			final int[][] ps = new int[h + 1][w + 1];
			for (int i = 1; i <= h; i++) {
				final int j = i;
				setAll(ps[i], k -> k > 0 ? nextInt() + ps[j - 1][k] + ps[j][k - 1] - ps[j - 1][k - 1] : 0);
			}
			return ps;
		}

		public long[][] nextLongPrefixSum(final int h, final int w) {
			final long[][] ps = new long[h + 1][w + 1];
			for (int i = 1; i <= h; i++) {
				final int j = i;
				setAll(ps[i], k -> k > 0 ? nextLong() + ps[j - 1][k] + ps[j][k - 1] - ps[j - 1][k - 1] : 0);
			}
			return ps;
		}

		public int[][][] nextIntPrefixSum(final int x, final int y, final int z) {
			final int[][][] ps = new int[x + 1][y + 1][z + 1];
			for (int a = 1; a <= x; a++)
				for (int b = 1; b <= y; b++) {
					final int A = a, B = b;
					setAll(ps[A][B], c -> c > 0 ? nextInt() + ps[A - 1][B][c] + ps[A][B - 1][c] + ps[A][B][c - 1]
							- ps[A - 1][B - 1][c] - ps[A - 1][B][c - 1] - ps[A][B - 1][c - 1] + ps[A - 1][B - 1][c - 1] : 0);
				}
			return ps;
		}

		public long[][][] nextLongPrefixSum(final int x, final int y, final int z) {
			final long[][][] ps = new long[x + 1][y + 1][z + 1];
			for (int a = 1; a <= x; a++)
				for (int b = 1; b <= y; b++) {
					final int A = a, B = b;
					setAll(ps[A][B], c -> c > 0 ? nextLong() + ps[A - 1][B][c] + ps[A][B - 1][c] + ps[A][B][c - 1]
							- ps[A - 1][B - 1][c] - ps[A - 1][B][c - 1] - ps[A][B - 1][c - 1] + ps[A - 1][B - 1][c - 1] : 0);
				}
			return ps;
		}

		public int[] nextIntInverseMapping(final int n) {
			final int[] inv = new int[n];
			for (int i = 0; i < n; i++)
				inv[nextInt() - 1] = i;
			return inv;
		}

		private <T extends Collection<Integer>> T nextIntCollection(int n, final Supplier<T> supplier) {
			final T collection = supplier.get();
			while (n-- > 0) {
				collection.add(nextInt());
			}
			return collection;
		}

		public ArrayList<Integer> nextIntAL(final int n) {
			return nextIntCollection(n, () -> new ArrayList<>(n));
		}

		public HashSet<Integer> nextIntHS(final int n) {
			return nextIntCollection(n, () -> new HashSet<>(n));
		}

		public TreeSet<Integer> nextIntTS(final int n) {
			return nextIntCollection(n, TreeSet::new);
		}

		private <T extends Collection<Long>> T nextLongCollection(int n, final Supplier<T> supplier) {
			final T collection = supplier.get();
			while (n-- > 0) {
				collection.add(nextLong());
			}
			return collection;
		}

		public ArrayList<Long> nextLongAL(final int n) {
			return nextLongCollection(n, () -> new ArrayList<>(n));
		}

		public HashSet<Long> nextLongHS(final int n) {
			return nextLongCollection(n, () -> new HashSet<>(n));
		}

		public TreeSet<Long> nextLongTS(final int n) {
			return nextLongCollection(n, TreeSet::new);
		}

		private <T extends Collection<Character>> T nextCharacterCollection(int n, final Supplier<T> supplier) {
			final T collection = supplier.get();
			while (n-- > 0) {
				collection.add(nextChar());
			}
			return collection;
		}

		public ArrayList<Character> nextCharacterAL(final int n) {
			return nextCharacterCollection(n, () -> new ArrayList<>(n));
		}

		public HashSet<Character> nextCharacterHS(final int n) {
			return nextCharacterCollection(n, () -> new HashSet<>(n));
		}

		public TreeSet<Character> nextCharacterTS(final int n) {
			return nextCharacterCollection(n, TreeSet::new);
		}

		private <T extends Collection<String>> T nextStringCollection(int n, final Supplier<T> supplier) {
			final T collection = supplier.get();
			while (n-- > 0) {
				collection.add(next());
			}
			return collection;
		}

		public ArrayList<String> nextStringAL(final int n) {
			return nextStringCollection(n, () -> new ArrayList<>(n));
		}

		public HashSet<String> nextStringHS(final int n) {
			return nextStringCollection(n, () -> new HashSet<>(n));
		}

		public TreeSet<String> nextStringTS(final int n) {
			return nextStringCollection(n, TreeSet::new);
		}

		private <T extends Map<Integer, Integer>> T nextIntMultiset(int n, final Supplier<T> supplier) {
			final T collection = supplier.get();
			while (n-- > 0) {
				final int i = nextInt();
				collection.put(i, collection.getOrDefault(i, 0) + 1);
			}
			return collection;
		}

		public HashMap<Integer, Integer> nextIntMultisetHM(final int n) {
			return nextIntMultiset(n, () -> new HashMap<>(n));
		}

		public TreeMap<Integer, Integer> nextIntMultisetTM(final int n) {
			return nextIntMultiset(n, TreeMap::new);
		}

		private <T extends Map<Long, Integer>> T nextLongMultiset(int n, final Supplier<T> supplier) {
			final T multiSet = supplier.get();
			while (n-- > 0) {
				final long l = nextLong();
				multiSet.put(l, multiSet.getOrDefault(l, 0) + 1);
			}
			return multiSet;
		}

		public HashMap<Long, Integer> nextLongMultisetHM(final int n) {
			return nextLongMultiset(n, () -> new HashMap<>(n));
		}

		public TreeMap<Long, Integer> nextLongMultisetTM(final int n) {
			return nextLongMultiset(n, TreeMap::new);
		}

		private <T extends Map<Character, Integer>> T nextCharMultiset(int n, final Supplier<T> supplier) {
			final T multiSet = supplier.get();
			while (n-- > 0) {
				final char c = nextChar();
				multiSet.put(c, multiSet.getOrDefault(c, 0) + 1);
			}
			return multiSet;
		}

		public HashMap<Character, Integer> nextCharMultisetHM(final int n) {
			return nextCharMultiset(n, () -> new HashMap<>(n));
		}

		public TreeMap<Character, Integer> nextCharMultisetTM(final int n) {
			return nextCharMultiset(n, TreeMap::new);
		}

		private <T extends Map<String, Integer>> T nextStringMultiset(int n, final Supplier<T> supplier) {
			final T multiSet = supplier.get();
			while (n-- > 0) {
				final String s = next();
				multiSet.put(next(), multiSet.getOrDefault(s, 0) + 1);
			}
			return multiSet;
		}

		public HashMap<String, Integer> nextStringMultisetHM(final int n) {
			return nextStringMultiset(n, () -> new HashMap<>(n));
		}

		public TreeMap<String, Integer> nextStringMultisetTM(final int n) {
			return nextStringMultiset(n, TreeMap::new);
		}

		public int[] nextIntMultiset(final int n, final int m) {
			final int[] multiset = new int[m];
			for (int i = 0; i < n; i++) {
				final int value = nextInt() - 1;
				multiset[value] = multiset[value] + 1;
			}
			return multiset;
		}

		public int[] nextUpperCharMultiset(final int n) {
			return nextCharMultiset(n, 'A', 'Z');
		}

		public int[] nextLowerCharMultiset(final int n) {
			return nextCharMultiset(n, 'a', 'z');
		}

		public int[] nextCharMultiset(int n, final char l, final char r) {
			final int[] multiset = new int[r - l + 1];
			while (n-- > 0) {
				final int c = nextChar() - l;
				multiset[c]++;
			}
			return multiset;
		}
	}

	@SuppressWarnings("unused")
	private static final class FastPrinter implements AutoCloseable {
		private static final int MAX_INT_DIGITS = 11;
		private static final int MAX_LONG_DIGITS = 20;
		private static final int DEFAULT_BUFFER_SIZE = 65536;
		private static final byte[] TWO_DIGIT_NUMBERS = new byte[200];

		static {
			byte tens = '0', ones = '0';
			for (int i = 0; i < 100; i++) {
				TWO_DIGIT_NUMBERS[i << 1] = tens;
				TWO_DIGIT_NUMBERS[(i << 1) + 1] = ones;
				if (++ones > '9') {
					ones = '0';
					tens++;
				}
			}
		}

		private final byte[] buffer;
		private final boolean autoFlush;
		private final OutputStream out;
		private int pos = 0;

		public FastPrinter() {
			this(System.out, DEFAULT_BUFFER_SIZE, false);
		}

		public FastPrinter(final OutputStream out) {
			this(out, DEFAULT_BUFFER_SIZE, false);
		}

		public FastPrinter(final int bufferSize) {
			this(System.out, bufferSize, false);
		}

		public FastPrinter(final boolean autoFlush) {
			this(System.out, DEFAULT_BUFFER_SIZE, autoFlush);
		}

		public FastPrinter(final OutputStream out, final boolean autoFlush) {
			this(out, DEFAULT_BUFFER_SIZE, autoFlush);
		}

		public FastPrinter(final int bufferSize, final boolean autoFlush) {
			this(System.out, bufferSize, autoFlush);
		}

		public FastPrinter(final OutputStream out, final int bufferSize) {
			this(out, bufferSize, false);
		}

		public FastPrinter(final OutputStream out, final int bufferSize, final boolean autoFlush) {
			this.out = out;
			this.buffer = new byte[max(bufferSize, 64)];
			this.autoFlush = autoFlush;
		}

		@Override
		public void close() throws IOException {
			flush();
			if (out != System.out)
				out.close();
		}

		public void flush() {
			try {
				if (pos > 0)
					out.write(buffer, 0, pos);
				out.flush();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			pos = 0;
		}

		public void println() {
			ensureBufferSpace(1);
			buffer[pos++] = '\n';
			if (autoFlush) flush();
		}

		public void println(final int i) {
			ensureBufferSpace(MAX_INT_DIGITS + 1);
			fillBuffer(i);
			buffer[pos++] = '\n';
			if (autoFlush) flush();
		}

		public void println(final long l) {
			ensureBufferSpace(MAX_LONG_DIGITS + 1);
			fillBuffer(l);
			buffer[pos++] = '\n';
			if (autoFlush) flush();
		}

		public void println(final double d) {
			print(Double.toString(d), true);
		}

		public void println(final char c) {
			ensureBufferSpace(2);
			buffer[pos++] = (byte) c;
			buffer[pos++] = '\n';
			if (autoFlush) flush();
		}

		public void println(final boolean b) {
			ensureBufferSpace(4);
			fillBuffer(b);
			buffer[pos++] = '\n';
			if (autoFlush) flush();
		}

		public void println(final String s) {
			print(s, true);
		}

		public void println(final Object o) {
			if (o == null) return;
			if (o instanceof String s) {
				print(s, true);
			} else if (o instanceof Long l) {
				println(l.longValue());
			} else if (o instanceof Integer i) {
				println(i.intValue());
			} else if (o instanceof Double d) {
				print(d.toString(), true);
			} else if (o instanceof Boolean b) {
				println(b.booleanValue());
			} else if (o instanceof Character c) {
				println(c.charValue());
			} else {
				print(o.toString(), true);
			}
		}

		public void println(final BigInteger bi) {
			print(bi.toString(), true);
		}

		public void println(final BigDecimal bd) {
			print(bd.toString(), true);
		}

		public void print(final int i) {
			ensureBufferSpace(MAX_INT_DIGITS);
			fillBuffer(i);
			if (autoFlush) flush();
		}

		public void print(final long l) {
			ensureBufferSpace(MAX_LONG_DIGITS);
			fillBuffer(l);
			if (autoFlush) flush();
		}

		public void print(final double d) {
			print(Double.toString(d), false);
		}

		public void print(final char c) {
			ensureBufferSpace(1);
			buffer[pos++] = (byte) c;
			if (autoFlush) flush();
		}

		public void print(final boolean b) {
			ensureBufferSpace(3);
			fillBuffer(b);
			if (autoFlush) flush();
		}

		public void print(final String s) {
			print(s, false);
		}

		public void print(final Object o) {
			if (o == null) return;
			if (o instanceof String s) {
				print(s, false);
			} else if (o instanceof Long l) {
				print(l.longValue());
			} else if (o instanceof Integer i) {
				print(i.intValue());
			} else if (o instanceof Double d) {
				print(d.toString(), false);
			} else if (o instanceof Boolean b) {
				print(b.booleanValue());
			} else if (o instanceof Character c) {
				print(c.charValue());
			} else {
				print(o.toString(), false);
			}
		}

		public void print(final BigInteger bi) {
			print(bi.toString(), false);
		}

		public void print(final BigDecimal bd) {
			print(bd.toString(), false);
		}

		public void printf(final String format, final Object... args) {
			print(String.format(format, args), false);
		}

		public void printf(final Locale locale, final String format, final Object... args) {
			print(String.format(locale, format, args), false);
		}

		private void ensureBufferSpace(final int size) {
			if (pos + size > buffer.length) {
				try {
					out.write(buffer, 0, pos);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				pos = 0;
			}
		}

		private void print(final String s, final boolean newline) {
			fillBuffer(s);
			if (newline) {
				ensureBufferSpace(1);
				buffer[pos++] = '\n';
			}
			if (autoFlush) flush();
		}

		private void fillBuffer(final String s) {
			if (s == null) return;
			final int len = s.length();
			for (int i = 0; i < len; ) {
				ensureBufferSpace(1);
				int limit = min(buffer.length - pos, len - i);
				while (limit-- > 0) {
					buffer[pos++] = (byte) s.charAt(i++);
				}
			}
		}

		private void fillBuffer(final boolean b) {
			if (b) {
				buffer[pos++] = 'Y';
				buffer[pos++] = 'e';
				buffer[pos++] = 's';
			} else {
				buffer[pos++] = 'N';
				buffer[pos++] = 'o';
			}
		}

		private void fillBuffer(int i) {
			if (i == Integer.MIN_VALUE) {
				buffer[pos++] = '-';
				buffer[pos++] = '2';
				buffer[pos++] = '1';
				buffer[pos++] = '4';
				buffer[pos++] = '7';
				buffer[pos++] = '4';
				buffer[pos++] = '8';
				buffer[pos++] = '3';
				buffer[pos++] = '6';
				buffer[pos++] = '4';
				buffer[pos++] = '8';
				return;
			}
			boolean negative = (i < 0);
			if (negative) {
				i = -i;
				buffer[pos++] = '-';
			}
			final int numOfDigits = countDigits(i);
			int writePos = pos + numOfDigits;
			while (i >= 100) {
				int quotient = i / 100;
				int remainder = (i - quotient * 100) << 1;
				buffer[--writePos] = TWO_DIGIT_NUMBERS[remainder + 1];
				buffer[--writePos] = TWO_DIGIT_NUMBERS[remainder];
				i = quotient;
			}
			if (i < 10) {
				buffer[--writePos] = (byte) ('0' + i);
			} else {
				buffer[--writePos] = TWO_DIGIT_NUMBERS[(i << 1) + 1];
				buffer[--writePos] = TWO_DIGIT_NUMBERS[i << 1];
			}
			pos += numOfDigits;
		}

		private void fillBuffer(long l) {
			if ((int) l == l) {
				fillBuffer((int) l);
				return;
			}
			if (l == Long.MIN_VALUE) {
				buffer[pos++] = '-';
				buffer[pos++] = '9';
				buffer[pos++] = '2';
				buffer[pos++] = '2';
				buffer[pos++] = '3';
				buffer[pos++] = '3';
				buffer[pos++] = '7';
				buffer[pos++] = '2';
				buffer[pos++] = '0';
				buffer[pos++] = '3';
				buffer[pos++] = '6';
				buffer[pos++] = '8';
				buffer[pos++] = '5';
				buffer[pos++] = '4';
				buffer[pos++] = '7';
				buffer[pos++] = '7';
				buffer[pos++] = '5';
				buffer[pos++] = '8';
				buffer[pos++] = '0';
				buffer[pos++] = '8';
				return;
			}
			boolean negative = (l < 0);
			if (negative) {
				l = -l;
				buffer[pos++] = '-';
			}
			final int numOfDigits = countDigits(l);
			int writePos = pos + numOfDigits;
			while (l >= 100) {
				long quotient = l / 100;
				int remainder = (int) (l - quotient * 100) << 1;
				buffer[--writePos] = TWO_DIGIT_NUMBERS[remainder + 1];
				buffer[--writePos] = TWO_DIGIT_NUMBERS[remainder];
				l = quotient;
			}
			if (l < 10) {
				buffer[--writePos] = (byte) ('0' + l);
			} else {
				buffer[--writePos] = TWO_DIGIT_NUMBERS[(int) (l << 1) + 1];
				buffer[--writePos] = TWO_DIGIT_NUMBERS[(int) l << 1];
			}
			pos += numOfDigits;
		}

		private int countDigits(final int i) {
			if (i < 10) return 1;
			if (i < 100) return 2;
			if (i < 1000) return 3;
			if (i < 10000) return 4;
			if (i < 100000) return 5;
			if (i < 1000000) return 6;
			if (i < 10000000) return 7;
			if (i < 100000000) return 8;
			if (i < 1000000000) return 9;
			return 10;
		}

		private int countDigits(final long l) {
			if (l < 10000000000L) return 10;
			if (l < 100000000000L) return 11;
			if (l < 1000000000000L) return 12;
			if (l < 10000000000000L) return 13;
			if (l < 100000000000000L) return 14;
			if (l < 1000000000000000L) return 15;
			if (l < 10000000000000000L) return 16;
			if (l < 100000000000000000L) return 17;
			if (l < 1000000000000000000L) return 18;
			return 19;
		}

		public void println(final int a, final int b) {
			println(a, b, '\n');
		}

		public void println(final int a, final long b) {
			println(a, b, '\n');
		}

		public void println(final long a, final int b) {
			println(a, b, '\n');
		}

		public void println(final long a, final long b) {
			println(a, b, '\n');
		}

		public void println(final long a, final long b, final char delimiter) {
			ensureBufferSpace((MAX_LONG_DIGITS << 1) + 2);
			fillBuffer(a);
			buffer[pos++] = (byte) delimiter;
			fillBuffer(b);
			buffer[pos++] = '\n';
			if (autoFlush) flush();
		}

		public void print(final int a, final int b) {
			print(a, b, ' ');
		}

		public void print(final int a, final long b) {
			print(a, b, ' ');
		}

		public void print(final long a, final int b) {
			print(a, b, ' ');
		}

		public void print(final long a, final long b) {
			print(a, b, ' ');
		}

		public void print(final long a, final long b, final char delimiter) {
			ensureBufferSpace((MAX_LONG_DIGITS << 1) + 1);
			fillBuffer(a);
			buffer[pos++] = (byte) delimiter;
			fillBuffer(b);
			if (autoFlush) flush();
		}

		public void println(final double d, final int n) {
			print(d, n);
			println();
		}

		public void print(double d, int n) {
			if (n == 0) {
				print(round(d));
				return;
			}
			if (d < 0) {
				ensureBufferSpace(1);
				buffer[pos++] = '-';
				d = -d;
			}
			d += pow(10, -n) / 2;
			print((long) d);
			ensureBufferSpace(n + 1);
			buffer[pos++] = '.';
			d -= (long) d;
			while (n-- > 0) {
				d *= 10;
				buffer[pos++] = (byte) ((int) d + '0');
				d -= (int) d;
			}
			if (autoFlush) flush();
		}

		public void println(final int[] arr) {
			println(arr, '\n');
		}

		public void println(final long[] arr) {
			println(arr, '\n');
		}

		public void println(final char[] arr) {
			println(arr, '\n');
		}

		public void println(final boolean[] arr) {
			println(arr, '\n');
		}

		public void println(final String[] arr) {
			println(arr, '\n');
		}

		public void println(final Object... arr) {
			if (arr == null) return;
			for (final Object o : arr)
				println(o);
		}

		public void println(final int[] arr, final char delimiter) {
			print(arr, delimiter);
			println();
		}

		public void println(final long[] arr, final char delimiter) {
			print(arr, delimiter);
			println();
		}

		public void println(final char[] arr, final char delimiter) {
			print(arr, delimiter);
			println();
		}

		public void println(final boolean[] arr, final char delimiter) {
			print(arr, delimiter);
			println();
		}

		public void println(final String[] arr, final char delimiter) {
			print(arr, delimiter);
			println();
		}

		public void print(final int[] arr) {
			print(arr, ' ');
		}

		public void print(final long[] arr) {
			print(arr, ' ');
		}

		public void print(final char[] arr) {
			print(arr, ' ');
		}

		public void print(final boolean[] arr) {
			print(arr, ' ');
		}

		public void print(final String[] arr) {
			print(arr, ' ');
		}

		public void print(final Object... arr) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(arr[0]);
			for (int i = 1; i < len; i++) {
				print(' ');
				print(arr[i]);
			}
		}

		public void print(final int[] arr, final char delimiter) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(arr[0]);
			for (int i = 1; i < len; i++) {
				ensureBufferSpace(MAX_INT_DIGITS + 1);
				buffer[pos++] = (byte) delimiter;
				fillBuffer(arr[i]);
			}
			if (autoFlush) flush();
		}

		public void print(final long[] arr, final char delimiter) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(arr[0]);
			for (int i = 1; i < len; i++) {
				ensureBufferSpace(MAX_LONG_DIGITS + 1);
				buffer[pos++] = (byte) delimiter;
				fillBuffer(arr[i]);
			}
			if (autoFlush) flush();
		}

		public void print(final char[] arr, final char delimiter) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(arr[0]);
			int i = 1;
			while (i < len) {
				ensureBufferSpace(2);
				int limit = min(buffer.length - pos, len - i);
				while (limit-- > 0) {
					buffer[pos++] = (byte) delimiter;
					buffer[pos++] = (byte) arr[i++];
				}
			}
			if (autoFlush) flush();
		}

		public void print(final boolean[] arr, final char delimiter) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(arr[0]);
			for (int i = 1; i < len; i++) {
				ensureBufferSpace(4);
				buffer[pos++] = (byte) delimiter;
				fillBuffer(arr[i]);
			}
			if (autoFlush) flush();
		}

		public void print(final String[] arr, final char delimiter) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(arr[0], false);
			for (int i = 1; i < len; i++) {
				print(delimiter);
				print(arr[i], false);
			}
		}

		public <T> void println(final int[] arr, final IntFunction<T> function) {
			if (arr == null) return;
			for (final int i : arr)
				println(function.apply(i));
		}

		public <T> void println(final long[] arr, final LongFunction<T> function) {
			if (arr == null) return;
			for (final long l : arr)
				println(function.apply(l));
		}

		public <T> void println(final char[] arr, final Function<Character, T> function) {
			if (arr == null) return;
			for (final char c : arr)
				println(function.apply(c));
		}

		public <T> void println(final boolean[] arr, final Function<Boolean, T> function) {
			if (arr == null) return;
			for (final boolean b : arr)
				println(function.apply(b));
		}

		public <T> void println(final String[] arr, final Function<String, T> function) {
			if (arr == null) return;
			for (final String s : arr)
				println(function.apply(s));
		}

		public <T> void print(final int[] arr, final IntFunction<T> function) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(function.apply(arr[0]));
			for (int i = 1; i < len; i++) {
				print(' ');
				print(function.apply(arr[i]));
			}
		}

		public <T> void print(final long[] arr, final LongFunction<T> function) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(function.apply(arr[0]));
			for (int i = 1; i < len; i++) {
				print(' ');
				print(function.apply(arr[i]));
			}
		}

		public <T> void print(final char[] arr, final Function<Character, T> function) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(function.apply(arr[0]));
			for (int i = 1; i < len; i++) {
				print(' ');
				print(function.apply(arr[i]));
			}
		}

		public <T> void print(final boolean[] arr, final Function<Boolean, T> function) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(function.apply(arr[0]));
			for (int i = 1; i < len; i++) {
				print(' ');
				print(function.apply(arr[i]));
			}
		}

		public <T> void print(final String[] arr, final Function<String, T> function) {
			if (arr == null) return;
			final int len = arr.length;
			if (len == 0) return;
			print(function.apply(arr[0]));
			for (int i = 1; i < len; i++) {
				print(' ');
				print(function.apply(arr[i]));
			}
		}

		public void println(final int[][] arr2d) {
			println(arr2d, ' ');
		}

		public void println(final long[][] arr2d) {
			println(arr2d, ' ');
		}

		public void println(final char[][] arr2d) {
			println(arr2d, ' ');
		}

		public void println(final boolean[][] arr2d) {
			println(arr2d, ' ');
		}

		public void println(final String[][] arr2d) {
			println(arr2d, ' ');
		}

		public void println(final Object[][] arr2d) {
			println(arr2d, ' ');
		}

		public void println(final int[][] arr2d, final char delimiter) {
			if (arr2d == null) return;
			for (final int[] arr : arr2d)
				println(arr, delimiter);
		}

		public void println(final long[][] arr2d, final char delimiter) {
			if (arr2d == null) return;
			for (final long[] arr : arr2d)
				println(arr, delimiter);
		}

		public void println(final char[][] arr2d, final char delimiter) {
			if (arr2d == null) return;
			for (final char[] arr : arr2d)
				println(arr, delimiter);
		}

		public void println(final boolean[][] arr2d, final char delimiter) {
			if (arr2d == null) return;
			for (final boolean[] arr : arr2d)
				println(arr, delimiter);
		}

		public void println(final String[][] arr2d, final char delimiter) {
			if (arr2d == null) return;
			for (final String[] arr : arr2d)
				println(arr, delimiter);
		}

		public void println(final Object[][] arr2d, final char delimiter) {
			if (arr2d == null) return;
			for (final Object[] arr : arr2d) {
				print(arr[0]);
				for (int i = 1; i < arr.length; i++) {
					print(delimiter);
					print(arr[i]);
				}
				println();
			}
		}

		public <T> void println(final int[][] arr2d, final IntFunction<T> function) {
			if (arr2d == null) return;
			for (final int[] arr : arr2d) {
				print(arr, function);
				println();
			}
		}

		public <T> void println(final long[][] arr2d, final LongFunction<T> function) {
			if (arr2d == null) return;
			for (final long[] arr : arr2d) {
				print(arr, function);
				println();
			}
		}

		public <T> void println(final char[][] arr2d, final LongFunction<T> function) {
			if (arr2d == null) return;
			for (final char[] arr : arr2d) {
				print(arr, function);
				println();
			}
		}

		public <T> void println(final boolean[][] arr2d, final Function<Boolean, T> function) {
			if (arr2d == null) return;
			for (final boolean[] arr : arr2d) {
				print(arr, function);
				println();
			}
		}

		public <T> void println(final String[][] arr2d, final Function<String, T> function) {
			if (arr2d == null) return;
			for (final String[] arr : arr2d) {
				print(arr, function);
				println();
			}
		}
	}
}

JavaScript solution:
const hash = function(p, str) {
    return (p * 51n + BigInt(str.charCodeAt() - "a".charCodeAt()) + 11n) % (1000000000000000177n);
}
const main = function(input) {
    const [Q] = input[0].split(" ").map(Number);
    const TS = [];
    const d = {};
    const arr = new Array(Q + 1).fill(0);
    for (var i = 1; i < Q + 1; i++) {
        const [T, S] = input[i].split(" ");
        TS.push([Number(T), S]);
        let p = 0n;
        for (var k = 0; k < S.length; k++) {
            p = hash(p, S[k]);
        }
        if (T == 1 && d[p] == void 0) {
            d[p] = i - 1;
        }
    }
    for (var i = 0; i < TS.length; i++) {
        const [T, S] = TS[i];
        if (T == 2) {
            let p = 0n;
            let c = Q;
            for (var k = 0; k < S.length; k++) {
                p = hash(p, S[k]);
                if (d[p] != void 0 && c > d[p]) {
                    c = d[p]
                    if (c <= i) break;
                };
            }
            if (i < c) {
                arr[i]++;
                arr[c]--;
            }
        }
    }
    for (var i = 1; i < arr.length; i++) {
        arr[i] += arr[i - 1];
    }
    arr.pop();
    console.log(arr.join("\n"));
};

(async () => {
    const buffers = [];
    for await (const chunk of process.stdin) buffers.push(chunk);
    const buffer = Buffer.concat(buffers);
    const text = buffer.toString();
    main(text.split("\n"))
})()

Python solution:
import sys,bisect
from collections import deque, Counter, defaultdict
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
mod = 10**9+7

ans = 0

class Node(object):
   def __init__(self) -> None:
       self.children = {}
       self.value = 0
    
def find(node, key):
    for c in key:
        if c not in node.children:
            return False
        node = node.children[c]
    return node.value

def insertx(node, key):
    global ans
    for c in key:
        if c not in node.children:
            node.children[c] = Node()
        node = node.children[c]

    q = deque()
    q.append(node)
    while q:
        node = q.popleft()
        if node.value >= 1:
            ans -= node.value
        node.value = -1
        for c in node.children.keys():
            nextnode = node.children[c]
            if nextnode.value == -1:
                continue

            q.append(nextnode)
    return

def inserty(node, key):
    global ans
    for c in key:
        #print(node.children, node.value)
        if node.value == -1:
            return
        elif c not in node.children:
            node.children[c] = Node()

        node = node.children[c]
        
    if node.value != -1:
        node.value += 1 #B
        ans += 1
    return
        

Q = ii()
root = Node()
for _ in range(Q):
    t,s = input().split()
    t = int(t)
    if t==1:
        insertx(root,s)
    else:
        inserty(root,s)
    print(ans)

Ruby solution:
#トライ木を使う
q = STDIN.gets.to_i
next_nodes = []
road_cnt = [] #ここのノードを使った文字の個数
covered = [] #ノードがXによって埋められているか

# 新しいノードを作成するやつ。未使用ノードが出てきたYに
def create_node(next_nodes, road_cnt, covered)
  idx = next_nodes.size
  next_nodes << Array.new(26, -1) #小文字の分だけ
  road_cnt    << 0
  covered    << false 
  idx
end
create_node(next_nodes, road_cnt, covered)
answer = 0
q.times do
  t, s = STDIN.gets.split
  t = t.to_i

  node = 0
  path = []
  already_covered = false

  if t == 2
    #新しい文字を木に追加する
    s.each_byte do |b|
      path << node
      already_covered ||= covered[node]
      idx = b - 97
      node = next_nodes[node][idx] == -1 ? create_node(next_nodes, road_cnt, covered) : next_nodes[node][idx]
      next_nodes[path.last][idx] = node
    end
    path << node
    already_covered ||= covered[node]

    unless already_covered
      path.each { |n| road_cnt[n] += 1 }
      answer += 1
    end
  else
    # X を追加
    s.each_byte do |b|
      break if covered[node]
      path << node
      idx = b - 97
      node = next_nodes[node][idx] == -1 ? create_node(next_nodes, road_cnt, covered) : next_nodes[node][idx]
      next_nodes[path.last][idx] = node
    end

    unless covered[node]
      removed = road_cnt[node]
      if removed > 0
        path.each { |n| road_cnt[n] -= removed }
        road_cnt[node] = 0
        answer -= removed
      end
      covered[node] = true
    end
  end

  puts answer
end