CF91E Igloo Skyscraper

Today the North Pole hosts an Olympiad in a sport called... toy igloo skyscrapers' building! There are $ n $ walruses taking part in the contest. Each walrus is given a unique number from $ 1 $ to $ n $ . After start each walrus begins to build his own igloo skyscraper. Initially, at the moment of time equal to $ 0 $ , the height of the skyscraper $ i $ -th walrus is equal to $ a_{i} $ . Each minute the $ i $ -th walrus finishes building $ b_{i} $ floors. The journalists that are reporting from the spot where the Olympiad is taking place, make $ q $ queries to the organizers. Each query is characterized by a group of three numbers $ l_{i} $ , $ r_{i} $ , $ t_{i} $ . The organizers respond to each query with a number $ x $ , such that: 1\. Number $ x $ lies on the interval from $ l_{i} $ to $ r_{i} $ inclusive ( $ l_{i}

The first line contains numbers $ n $ and $ q $ ( $ 1

For each journalists' query print the number of the walrus $ x $ that meets the criteria, given in the statement. Print one number per line.