E-1or0_牛客周赛 Round 77

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 定义由 $n$ 个字符组成的二进制字符串 $s_1s_2\cdots s_n$ 的“自审值”为： $s_1 \operatorname{or} s_2 \operatorname{or} \cdots \operatorname{or} s_n$ 。
$\hspace{15pt}$ 现在，对于给定的字符串，你需要独立处理 $q$ 次询问。每一次询问给定一个区间 $[l, r]$ ，求解区间内全部连续子串的“自审值”之和。

$\hspace{15pt}$ 其中， $\operatorname{or}$ 表示按位或运算。如果您需要更多位运算相关的知识，可以参考 OI-Wiki的相关章节。
$\hspace{15pt}$ 子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

输入描述:

第一行输入一个整数  代表字符串的长度。
第二行输入一个长度为 、仅由  和  两个字符组成的字符串 ，代表给定的字符串。下标从  开始。

第三行输入一个整数  代表询问次数。
此后  行，每行输入两个整数  代表询问的区间。

输出描述:

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

示例1

输入

复制

输出

复制

5
1

说明

对于第一次询问，拆分出全部子区间：
区间  的“自审值”为 ；
区间  的“自审值”为 ；
区间  的“自审值”为 ；
区间  的“自审值”为 ；
区间  的“自审值”为 ；
区间  的“自审值”为 ；
综上所述，“自审值”之和为 。