I used 4 Joins and a Union
-I used the text to Colum tool with a hyphen to break the gaps and then add rows to fill in the gaps. I also used a formula to add the leading zeros as that was tricky.
Finally for the military addresses (AA,AP,AE) and others I used a formula to hard code the assignment
There were probably more elegant ways to do this, but my strategy was to isolate the records in Input 1 into 3 different categories based on the types of "Zip" given: entire state, rest of the state and the 1st 3 numbers of the zip.