定义由 个字符组成的二进制字符串 的“自审值”为：。 现在，对于给定的字符串，你需要独立处理 次询问。每一次询问给定一个区间 ，求解区间内全部连续子串的“自审值”之和。 其中， 表示按位或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。 子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

输入描述:

第一行输入一个整数 代表字符串的长度。第二行输入一个长度为 、仅由 和 两个字符组成的字符串 ，代表给定的字符串。下标从 开始。第三行输入一个整数 代表询问次数。此后 行，每行输入两个整数 代表询问的区间。

输出描述:

对于每一次询问，新起一行。输出一个整数，代表区间内全部连续子串的“自审值”之和。