題目背景
土豪大學的計算機系開了一門數(shù)字邏輯電路課，第一個實驗叫做“點亮數(shù)字人生”，要用最基礎的邏輯元件組裝出實際可用的電路。時間已經是深夜了，盡管實驗箱上密密麻麻的連線已經拆裝了好幾遍，小君同學卻依舊沒能讓她的電路正常工作。你能幫助她模擬出電路的功能，成功點亮她的數(shù)字人生嗎？

問題描述
本題中，你需要實現(xiàn)一個簡單的數(shù)字邏輯電路模擬器。如果你已經有了此方面的基礎，可以直接跳過本節(jié)。在閱讀時，也可以參照前兩個樣例的圖示和解釋，這有助于你更好地理解數(shù)字邏輯電路的工作原理。

數(shù)字邏輯電路是用來傳輸數(shù)字信號（也就是二進制信號）的電路。一般來說，數(shù)字邏輯電路可以分為兩大類，即組合邏輯（combinational logic）電路和時序邏輯（sequential logic）電路。在本題中，我們僅關注組合邏輯電路。這種電路僅由邏輯門（logical gate）構成。一個邏輯門可以理解為一個多輸入單輸出的函數(shù)，輸入端連接至少一個信號，而后經過一定的邏輯運算輸出一個信號。常見的邏輯門包括與（AND）、或（OR）、非（NOT）、異或（XOR）等，均與編程語言中的按位運算是對應的。

將一系列的邏輯門連接起來，就能構成具有特定功能的電路。它的功能可能很簡單（如一位二進制加法只需要一個異或門），也可能極其復雜（如除法）。無論復雜程度，這類電路的特點是：它不維持任何的狀態(tài)，任何時刻輸出只與輸入有關，隨輸入變化。真實世界中的邏輯器件由于物理規(guī)律的限制，存在信號傳播延時。為了簡單起見，本題中我們模擬的組合邏輯電路不考慮延時：一旦輸入變化，輸出立刻跟著變化。

考慮到組合邏輯電路的這一特性，設計時不能允許組合環(huán)路（combinational loop）的存在，即某邏輯門的輸入經過了一系列器件之后又被連接到了自己的輸入端。真實世界中，這種做法將導致電路變得不穩(wěn)定，甚至損壞元器件。因此，你也需要探測可能的環(huán)路。需要注意，環(huán)路的存在性與邏輯門的具體功能沒有任何關系；只要連接關系上存在環(huán)路，電路就無法正常工作。

輸入格式
輸入數(shù)據(jù)包括若干個獨立的問題，第一行一個整數(shù)
，滿足
。接下來依次是這
個問題的輸入，你需要對每個問題進行處理，并且按照順序輸出對應的答案。

每一個問題的輸入在邏輯上可分為兩部分。第一部分定義了整個電路的結構，第二部分定義了輸入和輸出的要求。實際上兩部分之間沒有分隔，順序讀入即可。

第一部分
第一行是兩個空格分隔的整數(shù)
，分別表示了整個電路的輸入和器件的數(shù)量，滿足
并且
。其中
和
都是與測試點編號有關的參數(shù)。

接下來
行，每行描述一個器件，編號從 1 開始遞增，格式如下：

FUNC k L_1 L_2 … L_k
None
其中 FUNC 代表具體的邏輯功能，
表示輸入的數(shù)量，后面跟著該器件的
個輸入端描述
，格式是以下二者之一：

Im：表示第 m 個輸入信號連接到此輸入端，保證
；
On：表示第 n 個器件的輸出連接到此輸入端，保證
。
所有可能的 FUNC 和允許的輸入端數(shù)量如下表所述：

FUNC 最少輸入數(shù)量 最多輸入數(shù)量 功能描述
NOT 1 1 非
AND 2
與
OR 2
或
XOR 2
異或
NAND 2
與非（先全部與后取非）
NOR 2
或非（先全部或后取非）
所有的器件均只有一個輸出，但這個輸出信號可以被用作多個器件的輸入。

第二部分
第一行是一個整數(shù)
，表示此電路需要運行
次。每次運行，都會給定一組輸入，并檢查部分器件的輸出是否正確。
滿足
，其中
是一個與測試點編號有關的參數(shù)。

接下來的
行為輸入描述，每一行的格式如下：

I_1 I_2 … I_M
None
每行有
個可能為 0 或 1 的數(shù)字，表示各個輸入信號（按編號排列）的狀態(tài)。

接下來的
行為輸出描述，每一行的格式如下：

s_i O_1 O_2 … O_s
None
第一個整數(shù)
表示需要輸出的信號數(shù)量。后面共有
個在
到
之間的數(shù)字，表示在對應的輸入下，組合邏輯完成計算后，需要輸出結果的器件編號。

注意 O 序列不一定是遞增的，即要求輸出的器件可能以任意順序出現(xiàn)。

輸出格式
對于輸入中的
個問題，你需要按照輸入順序輸出每一個問題的答案：

如果你檢測到電路中存在組合環(huán)路，則請輸出一行，內容是 LOOP，無需輸出其他任何內容。

如果電路可以正常工作，則請輸出
行，每一行包含
個用空格分隔的數(shù)字（可能為 0 或 1），依次表示“輸出描述”中要求的各個器件的運算結果。

樣例輸入1
1
3 5
XOR 2 I1 I2
XOR 2 O1 I3
AND 2 O1 I3
AND 2 I1 I2
OR 2 O3 O4
4
0 1 1
1 0 1
1 1 1
0 0 0
2 5 2
2 5 2
2 5 2
2 5 2
Data
樣例輸出1
1 0
1 0
1 1
0 0
Data
樣例1說明
本樣例只有一個問題，它定義的組合邏輯電路結構如下圖所示。其功能是一位全加器，即將三個信號相加，得到一個兩位二進制數(shù)。要求的器件 2 的輸出是向更高位的進位信號，器件 5 的輸出是本位的求和信號。

p3.jpg

對于第一組輸入 0 1 1，輸出是 1 0；對于第二組輸入 1 0 1，輸出恰好依舊是 1 0（但電路內部狀態(tài)不同）。

樣例輸入2
1
2 6
NOR 2 O4 I2
AND 2 O4 O6
XOR 2 O5 O1
NOT 1 O6
NAND 2 O2 O2
AND 2 I1 O3
2
0 0
1 0
3 2 3 4
6 1 2 3 4 5 6
Data
樣例輸出2
LOOP
Data
樣例2說明
本樣例也只有一個問題，它定義的組合邏輯電路結構如下圖所示。

p4.jpg

這是一個帶組合環(huán)路的電路，因此無法正常工作。特別地，其中最短的環(huán)路有以下三條：

6 - 2 - 5 - 3 - 6
4 - 1 - 3 - 6 - 4
2 - 5 - 3 - 6 - 2
評測用例規(guī)模與約定

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.*;public class DigitalMock {static StreamTokenizer st=new StreamTokenizer(new BufferedInputStream(System.in));static int nextInt() throws IOException{st.nextToken();return (int)st.nval;}static String next() throws IOException{st.nextToken();return st.sval;}static int Q;//問題個數(shù)static int m;//信號輸入個數(shù)static int n;//器件個數(shù)static Nop nops[]=new Nop[550];static int head[]=new int[550];static int ne[]=new int[50000];static int to[]=new int[50000];static int cnt=1;static int du[]=new int[550];static void init(){//初始化Arrays.fill(head,0);Arrays.fill(nops,null);Arrays.fill(ne,0);Arrays.fill(to,0);Arrays.fill(du,0);cnt=1;}static void add(int u,int v){to[cnt]=v;ne[cnt]=head[u];head[u]=cnt++;}public static void main(String[] args) throws IOException{Q=nextInt();for (int i = 0; i < Q; i++) {init();m=nextInt();n=nextInt();for (int i1 = 1; i1 <=n; i1++) {String type=next();int inputsNum=nextInt();for (int j = 0; j < inputsNum; j++) {String in=next();char t=in.charAt(0);int u=Integer.valueOf(in.substring(1));du[i1]++;//起始輸入點if(t=='I'){add(u+n,i1);}//其他器件else{add(u,i1);}}Nop nop = new Nop(type);nops[i1]=nop;}for (int k = 1; k <=m; k++) {nops[k+n]=new Nop("SUPER");}int s=nextInt();List<List<Integer>> inputs = new ArrayList<>();List<List<Integer>> ques = new ArrayList<>();for (int i1 = 0; i1 < s; i1++) {List<Integer> sign = new ArrayList<>();for (int i2 = 0; i2 < m; i2++) {sign.add(nextInt());}inputs.add(sign);}for (int p = 0; p < s; p++) {int num=nextInt();List<Integer> q = new ArrayList<>();for (int i1 = 0; i1 < num; i1++) {q.add(nextInt());}ques.add(q);}if(isLoop()==false){System.out.println("LOOP");continue;}for (int i1 = 0; i1 < s; i1++) {query(inputs.get(i1),ques.get(i1));}}}static void query(List<Integer> input,List<Integer> ques){for (int i = 1; i <=n; i++) {//清空所有信號nops[i].input=new ArrayList<>();}for (int i = 1; i <= input.size(); i++) {nops[i+n].output=input.get(i-1);}topo();ArrayList<Integer> res = new ArrayList<>();for (Integer que : ques) {res.add(nops[que].getOut());}for (int i = 0; i < res.size(); i++) {System.out.printf(res.get(i)+" ");}System.out.println();}static boolean isLoop(){int visnum=0;int rudu[];rudu=du.clone();Queue<Integer> q=new LinkedList<>();for (int i = 1; i <=m+n; i++) {if(rudu[i]==0)q.offer(i);}while (!q.isEmpty()){Integer x = q.poll();//出隊visnum++;//訪問點+1for(int i=head[x];i!=0;i=ne[i]){int y=to[i];rudu[y]--;if(rudu[y]==0){q.offer(y);}}}return visnum==m+n;}static void topo(){int rudu[];rudu=du.clone();Queue<Integer> q=new LinkedList<>();for (int i = 1; i <=m+n; i++) {if(rudu[i]==0)q.offer(i);}while (!q.isEmpty()){Integer x = q.poll();//出隊for(int i=head[x];i!=0;i=ne[i]){int y=to[i];rudu[y]--;nops[y].input.add(nops[x].getOut());if(rudu[y]==0){q.offer(y);}}}}
}
class Nop{//NOT/AND/OR/XOR/NAND/NOR/SUPER(指輸入信號節(jié)點，超級節(jié)點)String type;List<Integer> input;//輸入端int output=-1;//輸出端public Nop(String type) {this.type = type;this.input=new ArrayList<>();}public int getOut(){//計算輸出端結果if(output!=-1) return output;if(type.equals("NOT")){return input.get(0)==0?1:0;}else if(type.equals("SUPER")){return output;}else if(type.equals("AND")){for (Integer integer : input) {if(integer==0) return 0;}return 1;}else if(type.equals("OR")){for (Integer integer : input) {if(integer==1) return 1;}return 0;}else if(type.equals("XOR")){int res=0;for (Integer integer : input) {res^=integer;}return res;}else if(type.equals("NAND")){for (Integer integer : input) {if(integer==0) return 1;}return 0;}else{for (Integer integer : input) {if(integer==1) return 0;}return 1;}}
}