CF617E XOR and Favorite Number

Bob has a favorite number $ k $ and $ a_{i} $ of length $ n $ . Now he asks you to answer $ m $ queries. Each query is given by a pair $ l_{i} $ and $ r_{i} $ and asks you to count the number of pairs of integers $ i $ and $ j $ , such that $ l

N/A

N/A

In the first sample the suitable pairs of $ i $ and $ j $ for the first query are: ( $ 1 $ , $ 2 $ ), ( $ 1 $ , $ 4 $ ), ( $ 1 $ , $ 5 $ ), ( $ 2 $ , $ 3 $ ), ( $ 3 $ , $ 6 $ ), ( $ 5 $ , $ 6 $ ), ( $ 6 $ , $ 6 $ ). Not a single of these pairs is suitable for the second query. In the second sample xor equals $ 1 $ for all subarrays of an odd length.