Module: Moアルゴリズム

Problem

Evan はお気に入りの番号 k と長さ n の配列 a_i を持っています。 m 件のリクエストに答えるように求められます。

数値 l と r のペアによって与えられる各クエリについて、l ≤ i ≤ j ≤ r および xor となる整数 i と j のペアの数を見つける必要があります。 < br />
入力:
最初の行には整数 n、m、k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤  10) が含まれます。 ⁶) —それぞれ、配列の長さ、リクエスト数、エヴァンのお気に入りの数です。
2 行目には n 個の整数 ai (0 ≤ a_i ≤ 10⁶) — が含まれます。エヴァンの配列。
次に m 行があります。 i 番目の行には、数値 l_i と r_i (1 ≤ l_i ≤ r< sub>i ≤ n) i 番目のクエリを定義します。

出力:
質問への回答を m 行、入力に表示される順序で出力します。

例:
  <本体>

入力	出力
6 2 3 1 2 1 1 0 3 16 3 5	7 0
5 3 1 1 1 1 1 1 15 24 1 3	9 4 4