Implement a Singly Linked List

You are required to implement a singly linked list with the following operations:

• addAtHead val: Insert an element with value val at the beginning of the list.
• addAtTail val: Append an element with value val at the end of the list.
• addAtIndex index val: Insert an element with value val before the element at position index. If index == size, the node will be appended at the end. If index > size, the insertion is ignored.
• deleteAtIndex index: Delete the element at position index if the index is valid.
• get index: Return the value of the element at position index. If the index is invalid, return -1.

The operations will be provided via stdin, and you must output the result of each get operation to stdout (each on a new line).

The design of your data structure must follow the concept of linked lists. You may assume that all values are integers and that the initial list is empty.

Note: All operations should work in accordance with the definitions. For indices, note that when a new element is inserted using the addAtIndex operation, the allowed index is in the range \(0 \leq index \leq size\), where \(size\) is the current number of nodes in the list.

inputFormat

The first line of input contains a single integer \(Q\) representing the number of operations to perform. Each of the next \(Q\) lines contains a command. The commands are one of the following formats:

• addAtHead val
• addAtTail val
• addAtIndex index val
• deleteAtIndex index
• get index

All values are integers. The input is given via standard input (stdin).

outputFormat

For each get operation, output the returned integer on its own line. The output is written to standard output (stdout).

## sample

6
addAtHead 1
addAtHead 2
get 0
get 1
addAtIndex 1 3
get 1

2
1
3

</p>