Another String Query Problem

This time I’m going to introduce you to a new land, called String Land.

In String Land there are N (1 ≤ N ≤ 105) cities, numbered from 1 to N sequentially. In each city there lives a man who have a name and also have an attractiveness value. The name of the ith person is namei and the attractiveness value is ai. Every year, people from different countries travel to String Land. Every traveler has a name. When a person travel to the String Land, he/she is only allowed to visit a segment of cities which lies in the range [L, R] i.e. he/she can visit the ith city iff L ≤ i ≤ R for a specific traveler. For different traveler the allowable range of cities to travel can be different.

This is a companion discussion topic for the original entry at