Drone Path Queries

Problem Statement

Drone Path Queries Problem Description There is a delivery drone in an infinite 2-dimensional city grid. Initially, the drone starts at the coordinates (0,0). The drone follows a series of movement commands: N — move from point (a,b) to (a,b+1) (north) S — move from point (a,b) to (a,b-1) (south) W — move from point (a,b) to (a-1,b) (west) E — move from point (a,b) to (a+1,b) (east) You are given a sequence of n commands denoted by s. You have to answer m independent queries. In each query, you are given four integers a, b, l and r. The drone will follow the sequence of commands s but with the commands from l to r reversed (ie, the drone will execute commands in the order: s1, s2, ..., sl-1, sr, sr-1, ..., sl+1, sl, sr+1, ..., sn) You have to determine if the drone reaches the coordinate (a, b) at any point during its path. Input The first line contains two integers n and m - the no of commands and the no of queries respectively. The second line contains a string s of length n, consist