题目背景

By Zhang Shancheng

题目描述

话说冯翰文与张文翰是好朋友，一天他们都没有写语文作业，语文老师便罚他们抄自己的名字，但可悲的是老师只给了他们一张纸，一根笔，于是他们只能抄几个自己的名字后换人。更可悲的是，他们抄着抄着忘了自己各抄了几遍，于是语文老师说，他们要想知道还要抄几次，就要告诉他总共剩余的次数为长度为k的子串中 ”翰”字出现的次数与”文”字出现的次数的三次方的差（绝对值）的最小值。他们请求你帮他们计算一下这个问题。当然，作为强迫症患者，他们的语文老师不会只问他们一次的。

输入格式

输入文件名为hanwen.in。

第一行，一个字符串表示他们已经抄的名字的序列(w代表“文”，h代表“翰”)；

第二行，一个整数m表示询问个数。

第三到m+2 行，每行一个整数k，表示这次询问的子串长度。

输出格式

输入文件名为hanwen.out。

m个数，分别表示最少需要抄的次数。

输入输出样例

输入 #1

hwwhwhwhwhwhhwhwhwwhwhhw
1
5

输出 #1

19

说明/提示

【样例解释】

选取第1到第5位即可。

【数据规模与约定】

字符串的长度≤1000000,询问次数m≤100000,k≤字符串长度。