B'DTL engineers love partying in the weekend. Ela does, too! Unfortunately, she didn 't know how to dance yet. Therefore, she decided to take a dancing class. There are n students in the dancing class, including Ela. In the final project, n students will participate in a choreography described below. n students are positioned on the positive side of the Ox -axis. The i -th dancer is located at a_i > 0 . Some dancers will change positions during the dance (we 'll call them movable dancers), and others will stay in the same place during a choreography (we 'll call them immovable dancers). We distinguish the dancers using a binary string s of length n : if s_i equals '1 ', then the i -th dancer is movable, otherwise the i -th dancer is immovable. Let 's call the "positive energy value" of the choreography d > 0 . The dancers will perform "movements" based on this value. Each minute after the dance begins, the movable dancer with the smallest x -coordinate will start moving to the right and initiate a "movement". At the beginning of the movement, the dancer 's energy level will be initiated equally to the positive energy value of the choreography, which is d . Each time they move from some y to y+1 , the energy level will be decreased by 1 . At some point, the dancer might meet other fellow dancers in the same coordinates. If it happens, then the energy level of the dancer will be increased by 1 . A dancer will stop moving to the right when his energy level reaches 0 , and he doesn 't share a position with another dancer. The dancers are very well-trained, and each "movement" will end before the next minute begins. To show her understanding of this choreography, Ela has to answer q queries, each consisting of two integers k and m . The answer to this query is the coordinate of the m -th dancer of both types from the left at k -th minute after '...