CF302A Eugeny and Array

Eugeny has array $ a=a_{1},a_{2},...,a_{n} $ , consisting of $ n $ integers. Each integer $ a_{i} $ equals to -1, or to 1. Also, he has $ m $ queries: - Query number $ i $ is given as a pair of integers $ l_{i} $ , $ r_{i} $ $ (1

The first line contains integers $ n $ and $ m $ $ (1

Print $ m $ integers — the responses to Eugene's queries in the order they occur in the input.