Pishty and birthday

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A little boy Pishty lives in Khust  an ancient town in the best country of the world  Uzhlyandia (also Khust is a wonderful town with their own castle and smart bears, but this is not relevant for us). And he is celebrating his birthday today!
Citizens of Uzhlyandia love two things : cakes and goulash , but Pishty prefer cakes. So his friend Lotsy decided to buy N cakes, because a friend's birthday must be the best day of his life!
A cake can be thought of as a 4 × 4 square matrix, and in each cell of the matrix no more than 1 candle can be placed.
The two boys like to play a game, in which they extinguish candles.
They play in turns, with the birthday boy Pishty taking the first turn. In each turn, one of the boys picks a cake with burning candles on it, chooses a rectangle (ie. a submatrix ) which has burning candles in all its cells, and extinguishes all those candles. If a boy can't make a move, he loses. You should assume that they play optimally. No one likes to lose a game, even to their best friend!
Because Pishty and Lotsy are best friends, Lotsy wants to buy the best collection of cakes, and so he has M queries to make to the Chef. There are 2 types of queries :
 to find the winner in the game if it is played with only the cakes in the range [L; R]
 to change a matrix, denoting a cake at some position
Input
The first line contains one integer T , denoting the number of test cases. Then T test case descriptions follow.
The first line of the each description contains two integers N and M, denoting the number of cakes and the number of queries respectively.
The following 5 × N lines contain information about the N cakedenoting matrices (four lines of strings of four chars (without spaces), followed by an empty line). An element of a matrix equals 1 if there is a burning candle and 0 if there isn't anything.
Then the queries follow in one of the following formats:
 1 L R  to find the winner in the game where only the caked in the range [L; R] are used.
 2 pos matrix  to change the cakedenoting matrix at position pos to matrix
Here, 2 pos will be on the first line and matrix will be described in the next four lines. each of which will be a string of four chars, without spaces in between. There will be no empty line after these four lines.
Output
For each query of first type output a single line containing a string "Pishty", if Pishty will win, or "Lotsy" otherwise.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N, M ≤ 10^{5}
 1 ≤ L ≤ R ≤ N
 1 ≤ pos ≤ N
Subtasks
Subtask 1 : 20 points
 1 ≤ N, M ≤ 10
Subtask 2: 30 points
 1 ≤ N, M ≤ 1000
Subtask 3 : 50 points
 1 ≤ N, M ≤ 10^{5}
Example
Input: 1 3 6 0110 0000 0000 0001 0000 0000 0000 0000 1000 1000 0000 0000 1 1 1 1 2 2 1 3 3 1 1 3 2 2 0001 0010 0100 1000 1 1 3 Output: Pishty Lotsy Pishty Pishty Pishty
Author:  fekete 
Tester:  xcwgf666 
Editorial  https://discuss.codechef.com/problems/PSHTBRTH 
Tags  fekete, gametheory, march17, medium, segmenttree, spraguegrundy 
Date Added:  19022017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 