#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;

const int LOG = 18;
const int N = 1 << LOG;

/**
 * To count number of occurances of string
 * calculate sum of cnt on link subtree
 */

const int AL = 26;

struct Node
{
	int g[AL];
	int link;
	int len;
	int cnt;
	Node(): link(-1), len(0), cnt(1)
	{
		fill(g, g + AL, -1);
	}
};

struct Automaton
{
	vector<Node> a;
	int head;
	Automaton(): a(1), head(0) {}
	void add(char c)
	{
		// change to [0 AL)
		int ch = c - 'a';
		int nhead = SZ(a);
		a.PB(Node());
		a[nhead].len = a[head].len + 1;
		int cur = head;
		head = nhead;
		while (cur != -1 && a[cur].g[ch] == -1)
		{
			a[cur].g[ch] = head;
			cur = a[cur].link;
		}
		if (cur == -1)
		{
			a[head].link = 0;
			return;
		}
		int p = a[cur].g[ch];
		if (a[p].len == a[cur].len + 1)
		{
			a[head].link = p;
			return;
		}
		int q = SZ(a);
		a.PB(Node());
		a[q] = a[p];
		a[q].cnt = 0;
		a[q].len = a[cur].len + 1;
		a[p].link = a[head].link = q;
		while (cur != -1 && a[cur].g[ch] == p)
		{
			a[cur].g[ch] = q;
			cur = a[cur].link;
		}
	}
};

struct Fenwick
{
	int n;
	VI t1, t2;
	
	Fenwick(int _n = 0)
	{
		_n = max(_n, 2);
		n = 1 << (32 - __builtin_clz(_n - 1));
		t1.assign(n, -N);
		t2.assign(n, -N);
	}
	
	void upd(int i, int x)
	{
		for (int j = i; j < n; j |= j + 1)
			t1[j] = x;
		for (int j = n - 1 - i; j < n; j |= j + 1)
			t2[j] = x;
	}
	int query(int l, int r)
	{
		int ans = -N;
		for (int j = r; j >= 0; j = (j & (j + 1)) - 1)
		{
			if ((j & (j + 1)) >= l)
				ans = max(ans, t1[j]);
		}
		for (int j = n - 1 - l; j >= 0; j = (j & (j + 1)) - 1)
		{
			if ((j & (j + 1)) >= n - 1 - r)
				ans = max(ans, t2[j]);
		}
		return ans;
	}
};

VI g[N];
int tin[N], tout[N], t;
int par[LOG][N];

void dfs(int v)
{
	tin[v] = t++;
	FOR(i, 1, LOG)
		par[i][v] = par[i - 1][par[i - 1][v]];
	for (int to : g[v])
	{
		if (to != par[0][v])
		{
			par[0][to] = v;
			dfs(to);
		}
	}
	tout[v] = t;
}

pair<LL, VI> f(const string& s, int w)
{
	int n = SZ(s);
	Automaton a;
	VI nodes;
	LL cntInit = 0;
	FOR(i, 0, n)
	{
		a.add(s[i]);
		nodes.PB(a.head);
		if (i < w)
			cntInit += a.a[a.head].len - a.a[a.a[a.head].link].len;
	}
	FOR(i, 0, SZ(a.a))
		g[i].clear();
	t = 0;
	FOR(i, 1, SZ(a.a))
		g[a.a[i].link].PB(i);
	dfs(0);
	Fenwick fw(SZ(a.a));
	auto maxEndpos = [&](int v)
	{
		return fw.query(tin[v], tout[v] - 1);
	};
	VI res(n - w);
	FOR(i, 0, n)
	{
		if (i >= w)
		{
			int v = nodes[i];
			if (maxEndpos(v) - a.a[a.a[v].link].len < i - w)
			{
				RFOR(j, LOG, 0)
				{
					int p = par[j][v];
					if (p != 0 && maxEndpos(p) - a.a[a.a[p].link].len < i - w)
					{
						v = p;
					}
				}
				v = par[0][v];
			}
			res[i - w] = v == 0 ? w + 1 : max(i - maxEndpos(v), w + 1 - a.a[v].len);
		}
		fw.upd(tin[nodes[i]], i);
	}
	return {cntInit, res};
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	string s;
	int q, w;
	cin >> s >> q >> w;
	int n = SZ(s);
	auto [c1, d1] = f(s, w);
	reverse(ALL(s));
	auto [c2, d2] = f(s, w);
	reverse(ALL(d2));
	vector<LL> ans(n - w + 1);
	ans[0] = c1;
	FOR(i, 0, n - w)
		ans[i + 1] = ans[i] + d1[i] - d2[i];
	assert(ans.back() == c2);
	while (q--)
	{
		int i;
		cin >> i;
		i--;
		cout << ans[i] << "\n";
	}
	return 0;
}