SP30738 ADACOINS - Ada and Coins

Ada the Ladybug has several coins in her wallet. She is wondering, how many different values \[sum of some subset of coins\] is she able to make (in given range).

The first line contains two integer numbers **1 , the number of coins and number of queries.** The next line contains **N** integer numbers **1 , the values of coins in Ada's wallet.** Afterward, **Q** lines follow, each containing two integers **1 , **b**eginning and **e**nd of range, for which ada wants to know the answer**

For each query, output the number of distinct values Ada can generate in given range.