$b=0|rand($m=1000000007);
$B=0|rand($M=1000000005);
$h[0]=$H[0]=1;
$h[$_]=$h[$_-1]*$b%$m,$H[$_]=$H[$_-1]*$B%$M for 1..<>;
$h{0}{0}=0;
	($q,$L,$R,$K)=glob,
	'!'eq$q?
		$h{$h+=$K*($h[$L]-$h[$R])}{$H+=$K*($H[$L]-$H[$R])}//=$.-1
	:
		print$h{$h}{$H}+0,$/
while<>