Syaro acted the role of the thief Lapin during Fleur du Lapin opening hours. But unfortunately, dueto her lack of acting skills, all the attention was drawn away by other characters. So she made an appointment with Coco, Chino, Rize and Chiya to watch the Lapin TV series in the Rabbit House together at night. Syaro is watching TV while learning the movements of the thief Lapin

After watching the TV series, Rize, Chiya and Syaro left. Cocoa and Chino watched them leave atthe door of Rabbit House

When returning to Chino’s room, Cocoa suddenly remembered:

”I forgot to do my homework. Lapin stole my time!”

Cocoa’s teacher gave two arrays ofnnumbers A= [a_1, a_2, a_3, ..., a_n], B= [b_1, b_2, b_3, ..., b_n] Then lether use these numbers and a number w to form a n×n matrix M (index started from 1):

And let her find the determinant det(M) of this matrix M.

Cocoa’s inspiration flashed, relying on her math skills, quickly calculated det(M). But Chino con-sidered that Cocoa looks silly , she must be wrong. Because Cocoa always does Chino a disservice when Rabbit House is open, and Chino always helps her clean up the mess. She changed several numbers in the array A and B, and gave w arbitrarily, and let Cocoa do the calculation again to seeif it was right. Can you help Chino calculate the value of det(M) so that she can quickly help Cocoa check whether it is correct? And Cocoa also wants to finish her homework and go to bed as soon as possible.

The first line is two integers n, Q \ (2≤n, Q≤100000) . Q means there are Q operations. The n integers in the second line represent the array A, where each integer a_i satisfies |a_i|≤10^9.The n integers in the third line represent the array B, where each integer b_i satisfies |b_i|≤10^9 .In the next Q line, there are three input types, representing three operations:

• 1p x It means that the number in the array A whose index is p is changed to an integer x, 1≤p≤n,|x|≤10^9.
• 2 p x It means that the number in the array B whose index is p is changed to an integer x, 1≤p≤n,|x|≤10^9.
• 3 w Represents the given integer w,|w|≤10^9.

For each operation 3, output the value of det(M). Since the value of det(M) is too large, please output it after modulo 10^9+ 7