Suppose that $L$ and $K$ lie on the circumcircle of $ABD$ and $ADC$, respectively.

Note that $\angle LAB = 90^\circ - \angle ABL = 90^\circ - \angle ADL = 90^\circ - \angle ACB$. Similarly we have $\angle CAK = 90^\circ - \angle CBA$. Summing these two implies that $\angle LAK = 2\angle BAC$. Denote by $T$ the intersection of $BL$, $CK$, then
$$\angle TBC = 180^\circ - \angle CBA - \angle ABL = 180^\circ - \angle CBA - \angle ACB = \angle BAC,$$
and similarly $\angle TCB = \angle BAC$. Therefore $ABC$ is an isosceles triangle and $\angle CTB = 180^\circ - 2\angle BAC$. Similarly, one can show that $\angle CSB = 180^\circ - 2\angle BAC$ and so quadrilateral $BCTS$ is cyclic. Properties of $S$ imply that $A$ is the $S$-excenter of the triangle $BCS$ and so $SA$ is the angle bisector of $\angle BSC$. Let $M$ be the midpoint of the arc $BC$ (the one that does not contain $S$) in the circumcircle of $BCS$. Clearly $M$ lies on $SA$.
On the other hand, since triangle $BTC$ is isosceles, $MT$ is a diagonal of the circumcircle of $BCS$. Thus, we can conclude that
$$\angle AST = \angle MST = 90^\circ = \angle AKT = \angle ALT.$$
This implies $AKLS$ is cyclic as desired. ■