Write a C program for the following:

Create a doubly linked list. The elements will be entered till the user enters -999.

-999 will not be taken as the input to the list, just to end the entering.

Make sure one of the entered elements is 35..

Insert a new element after the existing linked list element 35. If there are more than one occurrence of 35, give user the choice where the new element must be inserted.

Sample Input/Output

Input

35 19 32 45 35 39 -999

-56

Output

2 occurrence of 35 found.

Where should the insertion occur?

Input

1

Output

35 -56 19 32 45 35 39

__________________________ --- Input --- 19 32 45 39 -999

--- Expected output (text)--- At least one element must be 35. _________________________________ --- Input --- 35 39 42 55 35 64 -999 39 --- Expected output (text)--- 2 occurrence of 35 found. Where should the insertion occur?

Input

2

Output

35 39 42 55 35 39 64 _______________________________

--- Input --- 35 35 35 55 85 64 -999 -86 --- Expected output (text)--- 3 occurrence of 24 found. Where should the insertion occur?

Input

2

Output

35 35 -86 35 55 85 64 __________________________________ --- Input --- 35 35 35 35 55 85 64 -999 -86

--- Expected output (text)--- 4 occurrence of 35 found. Where should the insertion occur?

Input

1

Output

35 -86 35 35 35 55 85 64 ____________________________________ --- Input --- -999 --- Expected output (text)--- At least one element must be 35. ____________________________