Description

Yanami Anna asked Nukumizu Kazuhiko for help with losing her weight by locking all the snacks in a safe.（保險箱）To make sure her weight loss plan succeeded, Nukumizu came up with a special password generation method:

1. Perform T operations on a string S of length N.
2. Each operation shifts all characters from position L to position R forward by M positions. For example, moving 'a' forward by 3 results in 'd'.
   If the movement exceeds 'z', it wraps around to 'a' (e.g., 'x' moved forward by 3 becomes 'a'). 
   If we need to move back from 'a', it wraps around to 'z' (e.g., 'c' moved backward by 3 becomes 'z').

Unfortunately, after locking the safe, you realized your snacks were locked inside too! Luckily, Nukumizu recorded the password creation process. By following these steps in order, you can retrieve the password and save your snacks.

Input

The first line of input contains T, N and a string S of length N. T is ths number of operations, and the string S will only contain lowercase letters.
This is followed by T lines, each containing three numbers L , R and M , indicating that all characters from position L to position R in the string should be shifted by M positions.

Constraints

• 1 ≤ T, N ≤ 10⁶
• -10⁹ ≤ M ≤ 10⁹
• 1 ≤ L ≤ R ≤ N

​Subtasks

• Testcases 1 ~ 3: 1 ≤ T ≤ 1000
• Testcases 4 ~ 6: No additional restrictions.

Output

Output the string S after T operations.

 

Please remember to print "\n" at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss