Read problems statements in Mandarin Chinese  and Russian. 

Chef likes strings a lot but moreover he likes good strings. Chef calls a string str a good string if str starts and ends at different characters. For eg : strings such as abab , baccba , abc are all good strings whereas strings like aba, baab , baacaab are not good at all .
Today, Chef has a special string P consisting of lower case letters "c" , "h" , "e" and "f" only. Chef wants to make some queries about his string P.
Each of chef's query has the following form a b L R. For a given query, Chef wants to count the number of good strings which starts at letter a and ends at letter b such that starting index S_{i} and ending index E_{i} of a chosen substring satisfies L ≤ S_{i} < E_{i} ≤ R.
NOTE
Two substrings P_{1} and P_{2} are considered to be different if either S_{1} != S_{2} or E_{1} != E_{2} where S_{1},E_{1} and S_{2},E_{2} are the starting and ending index of string P_{1} and string P_{2} respectively.
Chef is not able to accomplish this task efficiently. Can you help him ? 

------ Input ------ 

First line of the input contains a string P denoting the chef's special string. Next line of the input contains a single integer Q denoting the number of chef's queries. Next Q lines of the input contains four space separated parameters where the first two parameters are characters denoting a and b respectively and rest two are integers denoting L and R respectively.

------ Output ------ 

For each chef's query, print the required answer.

------ Constraints ------ 

$1 ≤ |P| ≤ 10^{6}$
$1 ≤ Q ≤ 10^{6}$
$1 ≤ L ≤ R ≤ |P|$
$P,a,b belongs to the set of lower case letters [c,h,e,f] and a != b. 		
$$All test files are strictly according to constraints.$

------ Subtasks ------ 

$ Subtask #1: 1≤|P|,Q≤10^{4} : 27 pts$
$ Subtask #2: 1≤|P|,Q≤10^{5} : 25 pts$
$ Subtask #3: 1≤|P|,Q≤10^{6} : 48 pts$

------ Warning ------ 

Large test data set, Prefer to use faster input/output methods .

----- Sample Input 1 ------ 
checfcheff
5
c h 1 10
c f 1 10
e c 1 10
c f 1 5
c f 6 10
----- Sample Output 1 ------ 
4
8
2
2
2
----- explanation 1 ------ 
Q1 : good strings are ch , checfch , cfch , ch 
Q2 : good strings are checf , checfchef , checfcheff , cf , cfchef , cfcheff , chef , cheff

Difficulty: MEDIUM_HARD
Tags: String algorithms

Preprocessing

Range queries

Segment trees revisited

Data structures
Skill types: Data structures

Range queries

Starter code:

Solutions:
def main():
	P = input()
	Q = int(input())
	LetterCount = {'c': 0, 'h': 0, 'e': 0, 'f': 0}
	LetterCountList = {'c': list(), 'h': list(), 'e': list(), 'f': list()}
	ways = {'ch': list(), 'ce': list(), 'cf': list(), 'hc': list(), 'he': list(), 'hf': list(), 'eh': list(), 'ec': list(), 'ef': list(), 'fe': list(), 'fc': list(), 'fh': list()}
	for x in ways:
		ways[x].append(0)
	LetterCount[P[0]] = 1
	LetterCountList['c'].append(LetterCount['c'])
	LetterCountList['h'].append(LetterCount['h'])
	LetterCountList['e'].append(LetterCount['e'])
	LetterCountList['f'].append(LetterCount['f'])
	for i in range(1, len(P)):
		LetterCount[P[i]] = LetterCount[P[i]] + 1
		LetterCountList['c'].append(LetterCount['c'])
		LetterCountList['h'].append(LetterCount['h'])
		LetterCountList['e'].append(LetterCount['e'])
		LetterCountList['f'].append(LetterCount['f'])
		if P[i] == 'f':
			ways['cf'].append(ways['cf'][i - 1] + LetterCount['c'])
			ways['hf'].append(ways['hf'][i - 1] + LetterCount['h'])
			ways['ef'].append(ways['ef'][i - 1] + LetterCount['e'])
			ways['ch'].append(ways['ch'][i - 1])
			ways['fh'].append(ways['fh'][i - 1])
			ways['eh'].append(ways['eh'][i - 1])
			ways['ce'].append(ways['ce'][i - 1])
			ways['he'].append(ways['he'][i - 1])
			ways['fe'].append(ways['fe'][i - 1])
			ways['fc'].append(ways['fc'][i - 1])
			ways['hc'].append(ways['hc'][i - 1])
			ways['ec'].append(ways['ec'][i - 1])
		elif P[i] == 'h':
			ways['ch'].append(ways['ch'][i - 1] + LetterCount['c'])
			ways['fh'].append(ways['fh'][i - 1] + LetterCount['f'])
			ways['eh'].append(ways['eh'][i - 1] + LetterCount['e'])
			ways['cf'].append(ways['cf'][i - 1])
			ways['hf'].append(ways['hf'][i - 1])
			ways['ef'].append(ways['ef'][i - 1])
			ways['ce'].append(ways['ce'][i - 1])
			ways['he'].append(ways['he'][i - 1])
			ways['fe'].append(ways['fe'][i - 1])
			ways['fc'].append(ways['fc'][i - 1])
			ways['hc'].append(ways['hc'][i - 1])
			ways['ec'].append(ways['ec'][i - 1])
		elif P[i] == 'e':
			ways['ce'].append(ways['ce'][i - 1] + LetterCount['c'])
			ways['he'].append(ways['he'][i - 1] + LetterCount['h'])
			ways['fe'].append(ways['fe'][i - 1] + LetterCount['f'])
			ways['cf'].append(ways['cf'][i - 1])
			ways['hf'].append(ways['hf'][i - 1])
			ways['ef'].append(ways['ef'][i - 1])
			ways['ch'].append(ways['ch'][i - 1])
			ways['fh'].append(ways['fh'][i - 1])
			ways['eh'].append(ways['eh'][i - 1])
			ways['fc'].append(ways['fc'][i - 1])
			ways['hc'].append(ways['hc'][i - 1])
			ways['ec'].append(ways['ec'][i - 1])
		else:
			ways['fc'].append(ways['fc'][i - 1] + LetterCount['f'])
			ways['hc'].append(ways['hc'][i - 1] + LetterCount['h'])
			ways['ec'].append(ways['ec'][i - 1] + LetterCount['e'])
			ways['cf'].append(ways['cf'][i - 1])
			ways['hf'].append(ways['hf'][i - 1])
			ways['ef'].append(ways['ef'][i - 1])
			ways['ch'].append(ways['ch'][i - 1])
			ways['fh'].append(ways['fh'][i - 1])
			ways['eh'].append(ways['eh'][i - 1])
			ways['ce'].append(ways['ce'][i - 1])
			ways['he'].append(ways['he'][i - 1])
			ways['fe'].append(ways['fe'][i - 1])
	output = list()
	for x in range(0, Q):
		query = input()
		a = query.split()[0]
		b = query.split()[1]
		L = int(query.split()[2])
		R = int(query.split()[3])
		if L == R:
			output.append(0)
		else:
			key = str(a + b)
			if L != 1:
				cnta = LetterCountList[a][L - 1 - 1]
				cntb = LetterCountList[b][R - 1] - LetterCountList[b][L - 1]
				output.append(ways[key][R - 1] - cnta * cntb - ways[key][L - 1])
			else:
				output.append(ways[key][R - 1])
	for x in output:
		print(x)
main()


import sys

def numGood(P, a, b):
	count = 0
	aCount = 0
	for letter in P:
		if letter == a:
			aCount += 1
			continue
		if letter == b:
			count += aCount
	return count

def main():
	args = []
	for line in sys.stdin:
		args.append(line)
	P = args[0]
	Q = args[1]
	offset = 2
	letters = ['c', 'h', 'e', 'f']
	letterCount = {'c': [0], 'h': [0], 'e': [0], 'f': [0]}
	pairCount = {'c': {'h': [0], 'e': [0], 'f': [0]}, 'h': {'c': [0], 'e': [0], 'f': [0]}, 'e': {'c': [0], 'h': [0], 'f': [0]}, 'f': {'c': [0], 'h': [0], 'e': [0]}}
	for n in P[:-1]:
		letterCount[n].append(letterCount[n][-1] + 1)
		for letter in letters:
			if letter != n:
				letterCount[letter].append(letterCount[letter][-1])
			for letter2 in letters:
				if letter2 == n and letter != n:
					pairCount[letter][n].append(pairCount[letter][n][-1] + letterCount[letter][-1])
				elif letter != letter2:
					pairCount[letter][letter2].append(pairCount[letter][letter2][-1])
	for query in args[offset:]:
		(a, b, L, R) = query.split()
		L = int(L)
		R = int(R)
		cntA = letterCount[a][L - 1]
		cntB = letterCount[b][R] - letterCount[b][L - 1]
		print(pairCount[a][b][R] - pairCount[a][b][L - 1] - cntA * cntB)
main()


from itertools import accumulate

def prefixSum(seq):
	return tuple(accumulate(seq))
lookupDigit = {c: i for (i, c) in enumerate('chef')}
digits = tuple((lookupDigit[c] for c in input()))
nDigitsUpTo = tuple((prefixSum((1 if d == digit else 0 for d in digits)) for digit in range(4)))
nPairsEndingAt = tuple((tuple(([0] * len(digits) for b in range(4))) for a in range(4)))
enumerateDigits = enumerate(digits)
next(enumerateDigits)
for (i, snd) in enumerateDigits:
	for fst in (d for d in range(4) if d != snd):
		nPairsEndingAt[fst][snd][i] = nDigitsUpTo[fst][i - 1]
nPairsUpTo = tuple((tuple((prefixSum(nPairsEndingAt[fst][snd]) for snd in range(4))) for fst in range(4)))
for queryIdx in range(int(input())):
	(fst, snd, begin, end) = input().split()
	fst = lookupDigit[fst]
	snd = lookupDigit[snd]
	begin = int(begin) - 1
	end = int(end) - 1
	pairsUpTo = nPairsUpTo[fst][snd]
	count = pairsUpTo[end] - pairsUpTo[begin]
	if begin > 0:
		count -= nDigitsUpTo[fst][begin - 1] * (nDigitsUpTo[snd][end] - nDigitsUpTo[snd][begin])
	print(count)


def main():
	import sys
	S = input()
	c = [1 if S[0] == 'c' else 0]
	h = [1 if S[0] == 'h' else 0]
	e = [1 if S[0] == 'e' else 0]
	f = [1 if S[0] == 'f' else 0]
	ch = [0]
	ce = [0]
	cf = [0]
	hc = [0]
	he = [0]
	hf = [0]
	ec = [0]
	eh = [0]
	ef = [0]
	fc = [0]
	fh = [0]
	fe = [0]
	for i in range(1, len(S)):
		if S[i] == 'c':
			c.append(c[i - 1] + 1)
		else:
			c.append(c[i - 1])
		if S[i] == 'h':
			h.append(h[i - 1] + 1)
		else:
			h.append(h[i - 1])
		if S[i] == 'e':
			e.append(e[i - 1] + 1)
		else:
			e.append(e[i - 1])
		if S[i] == 'f':
			f.append(f[i - 1] + 1)
		else:
			f.append(f[i - 1])
	for i in range(1, len(S)):
		if S[i] == 'c':
			hc.append(hc[i - 1] + h[i - 1])
			ec.append(ec[i - 1] + e[i - 1])
			fc.append(fc[i - 1] + f[i - 1])
		else:
			hc.append(hc[i - 1])
			ec.append(ec[i - 1])
			fc.append(fc[i - 1])
		if S[i] == 'h':
			ch.append(ch[i - 1] + c[i - 1])
			eh.append(eh[i - 1] + e[i - 1])
			fh.append(fh[i - 1] + f[i - 1])
		else:
			ch.append(ch[i - 1])
			eh.append(eh[i - 1])
			fh.append(fh[i - 1])
		if S[i] == 'e':
			ce.append(ce[i - 1] + c[i - 1])
			he.append(he[i - 1] + h[i - 1])
			fe.append(fe[i - 1] + f[i - 1])
		else:
			ce.append(ce[i - 1])
			he.append(he[i - 1])
			fe.append(fe[i - 1])
		if S[i] == 'f':
			cf.append(cf[i - 1] + c[i - 1])
			hf.append(hf[i - 1] + h[i - 1])
			ef.append(ef[i - 1] + e[i - 1])
		else:
			cf.append(cf[i - 1])
			hf.append(hf[i - 1])
			ef.append(ef[i - 1])
	input()
	for x in sys.stdin:
		(a, b, L, R) = x.split()
		L = int(L) - 1
		R = int(R) - 1
		if a == 'c' and b == 'h':
			ans = ch[R]
			if L > 0:
				ans -= ch[L - 1] + c[L - 1] * (h[R] - h[L - 1])
		elif a == 'c' and b == 'e':
			ans = ce[R]
			if L > 0:
				ans -= ce[L - 1] + c[L - 1] * (e[R] - e[L - 1])
		elif a == 'c' and b == 'f':
			ans = cf[R]
			if L > 0:
				ans -= cf[L - 1] + c[L - 1] * (f[R] - f[L - 1])
		elif a == 'h' and b == 'c':
			ans = hc[R]
			if L > 0:
				ans -= hc[L - 1] + h[L - 1] * (c[R] - c[L - 1])
		elif a == 'h' and b == 'e':
			ans = he[R]
			if L > 0:
				ans -= he[L - 1] + h[L - 1] * (e[R] - e[L - 1])
		elif a == 'h' and b == 'f':
			ans = hf[R]
			if L > 0:
				ans -= hf[L - 1] + h[L - 1] * (f[R] - f[L - 1])
		elif a == 'e' and b == 'c':
			ans = ec[R]
			if L > 0:
				ans -= ec[L - 1] + e[L - 1] * (c[R] - c[L - 1])
		elif a == 'e' and b == 'h':
			ans = eh[R]
			if L > 0:
				ans -= eh[L - 1] + e[L - 1] * (h[R] - h[L - 1])
		elif a == 'e' and b == 'f':
			ans = ef[R]
			if L > 0:
				ans -= ef[L - 1] + e[L - 1] * (f[R] - f[L - 1])
		elif a == 'f' and b == 'c':
			ans = fc[R]
			if L > 0:
				ans -= fc[L - 1] + f[L - 1] * (c[R] - c[L - 1])
		elif a == 'f' and b == 'h':
			ans = fh[R]
			if L > 0:
				ans -= fh[L - 1] + f[L - 1] * (h[R] - h[L - 1])
		elif a == 'f' and b == 'e':
			ans = fe[R]
			if L > 0:
				ans -= fe[L - 1] + f[L - 1] * (e[R] - e[L - 1])
		print(ans)
main()