This assignment has to be programmed in Scheme!!

The Missionaries and Cannibals Problem Three missionaries and three cannibals come to the east side ofa river they wish to cross. There is a boat that will hold only two people, and any of the group is able to row it. If there are ever more cannibals than missionaries on any side of the river, the outnumbered missionaries will be killed Device a series of moves to get all the people to the west side safely Each problem state can be represented by a list of seven elements (NumOfMeast, NumOfCeast, NumOfMboat, NumOfCboat, NumOfMwest, NumOfCwest LocOfBoat), where each of the first 6 elements is a non-negative integer and the 7th element is a symbol indicating the location of the boat, which is either'e orw. For example, .(3 3 0 0 0 0 e) represents that there are 3 missionaries, 3 cannibals, and a boat, all at the east side of the river. Accessary Functions (10+20 points) 1. Define a function name nth that accepts two arguments: a list and an integer indicating the position of a top-level element in the list. The function returns the top-level element at the position indicated by the 2nd argument. It returns #fif the position is either greater than the list length or less than 1 . For example, (nth '((a b) (c d) e) 2) (c d), (nth((a b) (c d) e) 4) #f 2. Define a function Imlceb that describes the operation of loading a missionary and a cannibal from the east side to the boat. The function returns '0 if the boat is not on the east side or either are insufficient number of either missionary or cannibals on the east side. For example, (1mlceh'(3 3 0 0 0 0 e)) (2 2 1 100e) (Imlceb '(221100e)(112200 e) (lmlceb "(3 3 0 0 0 0 w)) "Ou Note that for this function, you don't have to be concerned with whether the resulting state is safe (ex., a 2 1 1 1 0 e)) or even possible (ex., "(11 2 2 0 0 e)). This can be handled by other functions such as unsafe and invalid as part of breadth first search. Breadth-first Search- Write scheme functions that uses breadth-first search to solve the missionary and cannibal problem for different number of missionaries and cannibals. For example of breadth first search, please refer to fwgc example. (50 points) Name the main function mc, which accepts two arguments indicating the initial state and the goal state. It returns the list of states from initial to the goal if a solution is found, '0 otherwise. For example, (mc.(220000e)'(000022w) ((220000 e)(111100e) (a11100 w) (110110 w) (110110e) (011110e) (O 11110 w) (010120 w) (010120e) (000220e) (000220w) (0 00022 w) Your program should solve the problem with at least 3 missionaries and 3 cannibals. This assignment is worth 80 points and is due on Monday (11/12) at class time. Submit softcopy of your scheme definitions in a single file on Moodle. Late submissions will be accepted until 12:00 PM Thursday (11/15). Nominal late penalty applies