You have a String of length N consisting of lowercase English letters. You have to encrypt the string using a sophisticated algorithm as follows:

1. There are $Q$ passes.

2.In each pass, an index $i$  is arbitrarily chosen and another index $j$  (not necessarily different), is determined by the following pseudo-code which runs for $t$ iterations where initially $j=i$  :

                            $k=j$

                           $j = (a*j +b) \%N$

                           $b=k$

3. The characters at index $i$ and $j$ are swapped at the end of each pass.

Find the encrypted string after Q passes.

Note: Large Input! Use Fast I/O.

INPUT

• First line of input contains two space-separated integers, $N$ ― the length of the string, and  $Q$ ― the number of passes.
• Next line contains a string of length $N$
• $Q$ lines follow, each containing four space-separated integers $i,a,b$  and $t$   describing the corresponding pass.

OUTPUT

Print a single line containing the encrypted String.

CONSTRAINTS

• $1<=N,Q<=10^5$
• $0<=i<N$
• $0<=a,b<=10^9$
• $0<=t<=1e 12$