test.cpp~

/*
#include <iostream>
#define m l + (r - l) / 2
#define lson rx * 2, l, m
#define rson rx * 2 + 1, m + 1, r
#define MAXN 10005
using namespace std;
int tree[MAXN], add[MAXN];
void Pushdown(int rx, int l, int r)
{
	if(add[rx])
	{
		add[rx * 2] += add[rx];
		add[rx * 2 + 1] += add[rx];
		tree[rx * 2] += (m - l + 1) * add[rx];
		tree[rx * 2 + 1] += (r - m) * add[rx];
		add[rx] = 0;
	}
}
void Bulid(int rx, int l, int r)
{
	add[rx] = 0;
	if(l == r)
	{
		cin >> tree[rx];
		return ;
	}
	Bulid(lson);
	Bulid(rson);
	tree[rx] = tree[rx * 2] + tree[rx * 2 + 1];
}
void Update_point(int rx, int l, int r, int pos, int v)
{
	if(l > pos || r < pos) return;
	if(l == r)
	{
		tree[rx] = v;
		return ;
	}
	Update_point(lson, pos, v);
	Update_point(rson, pos, v);
	tree[rx] = tree[rx * 2] + tree[rx * 2 + 1];
}
void Update_section(int rx, int l, int r, int L, int R, int v)
{
	if(R < l || L > r) return;
	if(L <= l && r <= R)
	{
		tree[rx] += (r - l + 1) * v;
		add[rx] += v;
		return ;
	}
	Update_section(lson, L, R, v);
	Update_section(rson, L, R, v);
	tree[rx] = tree[rx * 2] + tree[rx * 2 + 1];
}

int Query(int rx, int l, int r, int L, int R)
{
	if(R < l || L > r) return 0;
	Pushdown(rx, l, r);
	if(L <= l && r <= R) return tree[rx];
	return Query(lson, L, R) + Query(rson, L, R);
}
int main()
{
	int n, q;
	cin >> n >> q;
	Bulid(1, 1, n);
	while(q--)
	{
		int op;
		cin >> op;
		if(op == 1)
		{
			int pos, v;
			cin >> pos >> v;
			Update_point(1, 1, n, pos, v);
		}
		else if(op == 2)
		{
			int L, R, v;
			cin >> L >> R >> v;
			Update_section(1, 1, n, L, R, v);
		}
		else
		{
			int L, R;
			cin >> L >> R;
			cout << Query(1, 1, n, L, R) << endl;
		}
	}
	return 0;
}
*/
/*

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
struct node
{
	node *next[26];
	int cnt;
	node()
	{
		for(int i = 0; i < 26; ++i)
			next[i] = NULL;
		cnt = 0;
	}
};
void insert(node *root, char ch[], int pos)
{
	if(ch[pos] == '\0') return;
	if(root -> next[ch[pos] - 'a'] == NULL)
	{
		node *temp = new node;
		root -> next[ch[pos] - 'a'] = temp;
	}
	root -> next[ch[pos] - 'a'] -> cnt++;
	insert(root -> next[ch[pos] - 'a'], ch, pos + 1);
}
int query(node *root, char ch[], int pos)
{
	if(root -> next[ch[pos] - 'a'] == NULL) return 0;
	if(ch[pos + 1] == '\0') return root -> next[ch[pos] - 'a'] -> cnt;
	return query(root -> next[ch[pos] - 'a'], ch, pos + 1);
}
int main()
{
	node *root = new node;
	char word[100];
	while(true)
	{
		gets(word);
		if(strlen(word) == 0) break;
		insert(root, word, 0);
	}
	while(~scanf("%s", word))
		printf("%d\n", query(root, word, 0));
	return 0;
}
*/