Oops, one other piece of advice about flying around that part of Malaysia: If you book all your local flights with one airline, Malaysian, your total air cost will be about half what it would be if you even have one leg with any other airline. For the sake of the schedule, we wanted to fly one leg with Brunei's airline and that's how we found out about the one-airline deal. Go to Brunei while you are there. It is certainly different from either Sabah or Sarawak.