Description

Please complete the following functions:

請完成以下函式：

Node* InsertBeforeItem(Node* head, int item, int val): Create a new node with the value val and insert it before the "first" node with the value item. This function should return a pointer to the head node.

Node* InsertBeforeItem(Node* head, int item, int val)：創建一個新的節點(值為 val )，並插入到"第一個"值為 item 的節點前面，此函式須回傳指向 head 節點的指標。

void PrintList(Node* head): Print the values in the Linked List starting from the first node. This function does not need to return anything.

void PrintList(Node* head)：從第一個節點開始印出Linked List內的值，此函式不須進行回傳。

Input

The functions mentioned above "do not require" additional input values; everything needed will be passed as parameters directly.

上述函式都"不需要"額外自己輸入值，要用到的都會直接作為參數傳入!

The first line of input contains multiple integers, terminated by -1, representing the initial state of the Linked List.

第一行輸入包含多個整數，以 -1 作為結束，代表一開始 Linked List 的狀態。

Starting from the second line, there are multiple lines of input. Each line begins with a number choice representing the selected command:

第二行開始有多行輸入，每行第一個數字 choice 代表選擇的指令：

choice=0: Input ends

choice=0: 輸入結束

choice=1: InsertBeforeItem, followed by two numbers item and val

choice=1: InsertBeforeItem，後面輸入的兩個數字分別為 item, val

choice=2: PrintList

choice=2: PrintList

Output

Please see the description above.

請直接參考 Description。

Sample Input 1

87 42 19 65 93 -1
2
1 5 4
2
1 93 4
1 42 4
2
1 4 6
1 4 4
2
0

Sample Output 1

87->42->19->65->93
Can't find 5
87->42->19->65->93
87->4->42->19->65->4->93
87->6->4->4->42->19->65->4->93

Hint

此題預設 head 節點即為第一個節點。

Sample Code: