Sachverhalt: Sachverhalt: A. A._ betrieb erstmals im Sommer 2001 das Kulturfloss "S'isch im Fluss", das am Kleinbasler Rheinufer, zwischen der Mittleren Rheinbrücke und der Wettsteinbrücke, vertäut war. Auf dem Floss, das mit einer Bar verbunden war, fanden an 40 Tagen Konzerte statt. Die Veranstaltung war ein grosser Publikumserfolg, führte aber zu zahlreichen Beschwerden aus der Anwohnerschaft. A. A._ betrieb erstmals im Sommer 2001 das Kulturfloss "S'isch im Fluss", das am Kleinbasler Rheinufer, zwischen der Mittleren Rheinbrücke und der Wettsteinbrücke, vertäut war. Auf dem Floss, das mit einer Bar verbunden war, fanden an 40 Tagen Konzerte statt. Die Veranstaltung war ein grosser Publikumserfolg, führte aber zu zahlreichen Beschwerden aus der Anwohnerschaft. B. Nachdem A._ eine neue Bewilligung für den Betrieb des Musikflosses im Sommer 2002 beantragt hatte, fanden im Herbst 2001 erste Gespräche zwischen den Behörden, dem Veranstalter und den Anwohnern statt. Am 9. März 2002 wurde das Gesuch um Benutzung der Allmend für ein Musikfloss "S'isch im Fluss" mit Barbetrieb am Oberen Rheinweg in der Zeit vom 31. Juli bis 23. August 2002 im Kantonsblatt publiziert. Gegen das Gesuch gingen über zwanzig Einsprachen ein. B. Nachdem A._ eine neue Bewilligung für den Betrieb des Musikflosses im Sommer 2002 beantragt hatte, fanden im Herbst 2001 erste Gespräche zwischen den Behörden, dem Veranstalter und den Anwohnern statt. Am 9. März 2002 wurde das Gesuch um Benutzung der Allmend für ein Musikfloss "S'isch im Fluss" mit Barbetrieb am Oberen Rheinweg in der Zeit vom 31. Juli bis 23. August 2002 im Kantonsblatt publiziert. Gegen das Gesuch gingen über zwanzig Einsprachen ein. C. Mit Entscheid vom 13. Mai 2002 bewilligte das Tiefbauamt/Allmendverwaltung das Gesuch mit Auflagen und wies gleichzeitig die Einsprachen ab. Einem allfälligen Rekurs wurde die aufschiebende Wirkung entzogen. In der Bewilligung wurde die Anzahl der Konzerte auf 17 (zuzüglich eines Konzerts im Rahmen der Bundesfeier am 31. Juli, durchgeführt durch einen anderen Betreiber) festgelegt. An Sonntagen müsse das Floss geschlossen bleiben, und an je einem Werktag pro Woche dürfe keine Musik gespielt werden. Die Spielzeiten für die Konzerte wurden auf zweimal eine halbe Stunde, von 20.30 bis 21.00 Uhr und von 21.30 bis 22.00 Uhr, festgelegt, mit vorangehendem kurzen "Soundcheck" von maximal 30 Minuten Dauer. C. Mit Entscheid vom 13. Mai 2002 bewilligte das Tiefbauamt/Allmendverwaltung das Gesuch mit Auflagen und wies gleichzeitig die Einsprachen ab. Einem allfälligen Rekurs wurde die aufschiebende Wirkung entzogen. In der Bewilligung wurde die Anzahl der Konzerte auf 17 (zuzüglich eines Konzerts im Rahmen der Bundesfeier am 31. Juli, durchgeführt durch einen anderen Betreiber) festgelegt. An Sonntagen müsse das Floss geschlossen bleiben, und an je einem Werktag pro Woche dürfe keine Musik gespielt werden. Die Spielzeiten für die Konzerte wurden auf zweimal eine halbe Stunde, von 20.30 bis 21.00 Uhr und von 21.30 bis 22.00 Uhr, festgelegt, mit vorangehendem kurzen "Soundcheck" von maximal 30 Minuten Dauer. D. Gegen die Bewilligung erhoben X._, Y._ und die Z._ Rekurs an das Baudepartement. Am 12. August 2002 fand ein Hearing im Baudepartement statt, an dem die Behörden, die Anwohner und der Veranstalter teilnahmen und über die Erfahrungen mit der laufenden Veranstaltung "S'isch im Fluss" 2002 berichteten. Am 29. Januar 2003 wies das Baudepartement die Rekurse ab, soweit es darauf eintrat. D. Gegen die Bewilligung erhoben X._, Y._ und die Z._ Rekurs an das Baudepartement. Am 12. August 2002 fand ein Hearing im Baudepartement statt, an dem die Behörden, die Anwohner und der Veranstalter teilnahmen und über die Erfahrungen mit der laufenden Veranstaltung "S'isch im Fluss" 2002 berichteten. Am 29. Januar 2003 wies das Baudepartement die Rekurse ab, soweit es darauf eintrat. E. Gegen den Rekursentscheid reichten X._, Y._ und die Z._ Rekurs beim Regierungsrat des Kantons Basel-Stadt ein. Am 26. März 2003 überwies das Justizdepartement die Sache dem Verwaltungsgericht zum direkten Entscheid. Dieses wies die Rekurse am 5. Dezember 2003 ab, soweit auf sie einzutreten sei. E. Gegen den Rekursentscheid reichten X._, Y._ und die Z._ Rekurs beim Regierungsrat des Kantons Basel-Stadt ein. Am 26. März 2003 überwies das Justizdepartement die Sache dem Verwaltungsgericht zum direkten Entscheid. Dieses wies die Rekurse am 5. Dezember 2003 ab, soweit auf sie einzutreten sei. F. Gegen den verwaltungsgerichtlichen Entscheid erheben X._, Y._ und die Z._ Verwaltungsgerichtsbeschwerde und staatsrechtliche Beschwerde ans Bundesgericht. Sie beantragen, die Entscheide des Verwaltungsgerichts und des Baudepartements seien aufzuheben und das Baudepartement sei anzuweisen, inskünftig keine Bewilligungen für die gleiche Veranstaltung am gleichen Ort zu erteilen. F. Gegen den verwaltungsgerichtlichen Entscheid erheben X._, Y._ und die Z._ Verwaltungsgerichtsbeschwerde und staatsrechtliche Beschwerde ans Bundesgericht. Sie beantragen, die Entscheide des Verwaltungsgerichts und des Baudepartements seien aufzuheben und das Baudepartement sei anzuweisen, inskünftig keine Bewilligungen für die gleiche Veranstaltung am gleichen Ort zu erteilen. G. Das Baudepartement beantragt, die Beschwerden seien abzuweisen, soweit auf sie eingetreten werden könne. A._ schliesst auf Abweisung der Verwaltungsgerichtsbeschwerde; auf die staatsrechtliche Beschwerde sei nicht einzutreten. Das Verwaltungsgericht beantragt, beide Beschwerden seien abzuweisen. G. Das Baudepartement beantragt, die Beschwerden seien abzuweisen, soweit auf sie eingetreten werden könne. A._ schliesst auf Abweisung der Verwaltungsgerichtsbeschwerde; auf die staatsrechtliche Beschwerde sei nicht einzutreten. Das Verwaltungsgericht beantragt, beide Beschwerden seien abzuweisen. H. In seiner Vernehmlassung vom 23. Juni 2004 geht das BUWAL davon aus, dass die Lärmimmissionen der Veranstaltung die Anwohnerschaft in ihrem Wohlbefinden erheblich stören, und hält weitere betriebliche Massnahmen zur Reduktion der Lärmimmissionen für notwendig. Zu prüfen seien die Erhöhung der Anzahl veranstaltungsfreier Tage auf zwei pro Woche, die Reduktion auf drei laute Konzerte pro Woche, das zeitliche Vorverschieben einzelner Veranstaltungen (beispielsweise sogenannt ruhiger Konzerte nur bis 21.30) und eine weitere zeitliche Einschränkung des Barbetriebs. Den Beteiligten wurde Gelegenheit gegeben, sich zur Vernehmlassung des BUWAL zu äussern. Den Beteiligten wurde Gelegenheit gegeben, sich zur Vernehmlassung des BUWAL zu äussern. I. Als vorsorgliche Massnahme hatten die Beschwerdeführer beantragt, das Baudepartement sei anzuweisen, bis zum Vorliegen eines rechtskräftigen Entscheids keine Bewilligung für die Veranstaltung "S'isch im Fluss" am gleichen Ort zu erteilen. Auf dieses Gesuch trat der Präsident der I. öffentlichrechtlichen Abteilung am 26. März 2004 nicht ein: Gegenstand des bundesgerichtlichen Verfahrens sei nur die Bewilligung des Kulturflosses für den Sommer 2002; soweit die Beschwerdeführer sich gegen die Erteilung einer neuen Bewilligung für den Sommer 2004 wendeten, müssten sie ihre Rechte im kantonalen Bewilligungsverfahren wahren. 